闫氏dp思路流程
状态表示和状态转移
状态表示:用数组将所求问题的集合表示,以二维为例,难点在于i,j表示的含义确定。
之后寻找集合表示的属性,一般是求count,max,min。在状态转移之前对集合初始化的时候
一般max要置零,min取负无穷,数量要讨论启始情况和特殊情况
状态转移:转移考虑的是倒数第二步到最后一步的变换是什么,要求做到不重不漏,及对所有的可能情况表示
ps:慢慢总结,以及数据不大的情况用朴素就行
背包问题
01背包 题目链接
题目描述:
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
思考
从i件物品中取,总体积为j的集合的最大价值
要考虑的是在选第i个物品的时候此时背包的空间是否足够
初学难点:f[i][j]表示的意义是拥有最大属性的集合而不是有具体含义的数
状态转移的区分点在第i个物品选还是不选
朴素做法
#include <iostream>
#include <cstring>
// #include <algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N][N];
int n,m;
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout << f[n][m]<<endl;
return 0;
}
优化
二维数组的i对答案没影响即可删去,难点在于j为什么要倒序
看这里
ps:我也一知半解
2022.4.25 懂了
为什么要逆序
我们在对j进行遍历的话,如果是顺序遍历,那么当在更新f[j-w[i]]的时候,这里更新的值可能是
本轮所更新的,而本轮所更新的值显然是错误的,正确的值应该是上一轮确定的,而如果逆序的话,
f[j-w[i]]在更新的时候取的是上一轮的值,就不会出错,所以逆序是正确的
视频链接看这里:(https://www.bilibili.com/video/BV1kp4y1e794?spm_id_from=333.999.0.0)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int w[N],v[N];
int f[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout << f[m]<<endl;
return 0;
}
完全背包
题目描述
有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
思考
区别在于可以无限拿,这道题目的难点在于不知道在多元的情况下max的属性
我们通过推算得出
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v]+2*w , .....)
下式加w等于上式
所以状态转移 f[i][j]=max(f[i,j-v]+w , f[i-1][j])
朴素代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int w[N],v[N];
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
cout << f[n][m]<<endl;
return 0;
}
优化
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N],w[N];
int n,m;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=m;j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout << f[m]<<endl;
return 0;
}
多重背包问题1
题目链接
题目描述:有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
思考
多重背包1只是对01的加强,理解了01,这个一看就懂
朴素做法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N],s[N];
int n,m;
int f[N][N];
int main()
{
cin >> n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i]>>s[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
{
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
}
}
}
cout << f[n][m];
return 0;
}
优化
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int w[N],v[N],s[N];
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
f[j]=max(f[j],f[j-k*v[i]]+w[i]*k);
cout << f[m]<<endl;
return 0;
}
因为是倒序的缘故,那么接下来枚举的j都要比先前的j要来的小,所以当某个位置更新数据时,并不会调用其位置后面的数据,一定会是先调用其位置之前的旧数据,然后再将当前位置更新覆盖掉原来的旧数据,也就保证了数据更新的有序性。
orz
您才是大佬啊orz,跟您比我算不上什么