v[i]
储存 第i
个物体体积,w[i]
储存 第i
个物体价值
复习一下背包问题的状态:
f[i][j]表示 把前i
个物体,放入容量为j
的背包的最优解
状态划分:以第i
个物体的数量k
为标准(k
=0,1,2…)
f[i][j] = max( f[i][j] , f[i-1][j-k*c[i]] + k*w[i] )
最终的答案就是f[n][v]
k
的限制:
1:最基本条件
k
自然不可能无限大,至少也得满足:不考虑前i-1
个物体,只考虑第i
个物体不能超过容量j
也就是k*v[i]<=j
然而实际操作中k*v[i]
可能会超出int范围我们写的时候最好写作k<=j/v[i]
2:题目的附加条件
如果题目本身对某个物体有范围限制,我们要在满足条件1的基础之上并且满足k<=s[i]
可以发现完全背包就是只需要满足k<=j/v[i]
这个条件
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=j/v[i];k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
多重背包就是在完全背包基础之上满足k<=s[i]
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=j/v[i]&&k<=s[i];k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
01背包就是在完全背包基础之上满足k<=1
(多重背包的特殊情况,每个物体最多只能取一次)
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=j/v[i]&&k<=1;k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
这就是背包问题思路上的通法,但是01背包和多重背包可以对代码进行形式上的优化来降低时间复杂度,也就是大家平常见到的板子。
详情请看我的这两篇帖子
01 : https://www.acwing.com/file_system/file/content/whole/index/content/7265933/
多重:https://www.acwing.com/file_system/file/content/whole/index/content/7276298/