01背包问题
可以把问题拆分成两部分,集合划分。
左边是不含i的右边的含i的,那么左边的MAX就是f(i-1,j)//意思就是在前i-1个物品中选最大值,总量不超过j
右边的MAX由于不能直接推所以要利用i-1递推,也就是f(i-1,j-vi)+wi//意思就是总量变少了,总体减一个i的大小,加一个i的权值
最终,如果左右都超了,那么就判断大小,输出背包最终能存放的最大值。
二维DP
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];//表示状态
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
//f[0][0~m]=0默认是0,不用写
for(int i=1;i<=n;i++)
for(int j=1;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]);//右边要进行判断,如果超出了j那么不存在
}
cout<<f[n][m]<<endl;
return 0;
}
一维DP
f(i)只用到了f(i-1),且总量都是小于j的,所以可以转换为1维滚动数组来做
细节看注释
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];//表示状态
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
//f[0][0~m]=0默认是0,不用写
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)//改为从大到小枚举,用到的才是第i-1层的效果
{
//f[j]=f[j];恒等式可以不用
f[j]=max(f[j],f[j-v[i]]+w[i]);//如果从小到大枚举,那么最终算出来的j-vi是第i层的j-vi
//因为j-vi严格小于j整体持续循环,覆盖上一层循环结果
//f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
cout<<f[m]<<endl;
return 0;
}
补充:为什么是从大到小循环呢?
因为原先二维dp的左边是第i层,右边比较大小的那个f是第i-1层,这就要求一位dp的遍历必须是左边的j大于右边的j-v[i],这也就使得整体必须从大到小遍历。