背包问题
有n种物品,每种物品有自己体积(或价格或重量等等)c和价值w,每种物品可能有一个、可能有多个m、可能有无数个,我们有一个背包,背包的总体积为N,要求用这个背包装下价值尽可能多的物品,求该最大价值,背包可以不被装满。
根据物品的个数我们把背包问题分为0-1背包、多重背包和完全背包
背包问题通过动态规划方法解决,我们直接上一维dp的解决方法,dp[i]表示装了i体积物品的最大价值
0-1背包
每种物品只有一个,每个物品,我们可以装入背包也可以不装入背包
转移方程:
dp[i]=max(dp[i-c]+w, dp[i])
dp[i]表示没有装入背包的价值;dp[i-c]+w表示装入背包后的价值,需要给它挪出c的空间,所以有个i-c,它的价值为w,所以需要在dp[i-c]的基础上加上w
使用一维数组解决这个问题时,需要注意从后往前遍历整个体积,否则就会重复加入当前物品
for (int i=0; i < n; i++) { // 遍历n种物品
for (int j = N; j>= goods[i].c;j--) { // 从后往前遍历背包体积
dp[i] = max(dp[i-goods[i].c]+goods[i].w, dp[i]);
}
}
完全背包
每个物品的数量有无穷个
其实,这个问题的解决方法很简单,就是在0-1背包的基础上从前往后遍历背包体积
0-1背包中为了避免重复加入某个物品,所以从后往前遍历
而完全背包中,每个物品的数量是无穷的,所以可以重复加入
for (int i=0; i < n; i++) { // 遍历n种物品
for (int j = goods[i].c; j <= N; j++) { // 从后往前遍历背包体积
dp[i] = max(dp[i-goods[i].c]+goods[i].w, dp[i]);
}
}
多重背包
每个物品数量不定,所以我们得注意不能超过限制
转移方程:
dp[i]=max(dp[i- k * c]+ k * w, dp[i]),1<=k<=m
for (int i=0; i < n; i++) { // 遍历n种物品
for (int k = 1; k <= goods[i].m; k++) { // 遍历物品个数
for (int j = x; j >= k * goods[i].c;j--) { // 从后往前遍历背包体积
dp[j] = max(dp[j- k * goods[i].c] + k * goods[i].w, dp[j]);
}
}
}