网站开发历史,郴州网站建设推广服务,建设企业网站初始必备的六大功能,郑州网站制作哪家好背包问题是一种组合优化的问题#xff0c;它有多种变体#xff0c;但最常见的两种是0/1背包问题和完全背包问题。
0/1背包问题
问题描述#xff1a; 假设你有一个背包#xff0c;背包的容量为W#xff08;可以是重量或者体积等度量#xff09;#xff0c;同时有n个物品…背包问题是一种组合优化的问题它有多种变体但最常见的两种是0/1背包问题和完全背包问题。
0/1背包问题
问题描述 假设你有一个背包背包的容量为W可以是重量或者体积等度量同时有n个物品每个物品都有自己的重量w[i]和价值v[i]。现在的目标是选择一些物品放入背包使得背包中物品的总价值最大但背包的总重量不能超过W。
特点 每个物品只能选择一次即不能分割。 选择放入背包或者不放入背包。
解决方案
动态规划这是解决0/1背包问题最常见的方法。通过构建一个二维数组dp其中dp[i] [j]表示考虑前i个物品背包容量为j时的最大价值。状态转移方程为 dp[i] [j]max(dp[i−1] [j],dp[i−1] [j−w[i]]v[i]), dp[i] [j]max(dp[i−1] [j],dp[i−1] [j−w[i]]v[i]) 其中如果选择第i个物品则背包容量减去该物品的重量总价值加上该物品的价值如果不选择则总价值不变。
已知w[]和v[]
int[][] dp new int[n 1][m 1]for(int i 1; i n; i) {//遍历物品注意下标的对应关系这里都假设物品从下标1开始记录for(int j 1; j m; j) {//遍历容量if(j w[i])dp[i][j] Math.max(d[i-1][j], dp[i-1][j-w[i]] v[i]); }
}
但是我们观察动态规划方程发现对于考虑前i个物品的时候我们只需要用到i-1这一个状态所以我们能不能将二维的数组压缩成一维的呢答案显然是可以的
我们现在设dp[j]是容量j时的最大价值因为我们外层循环的i一直在自增所以对于上一次的dp[j]就相当与dp[i-1] [j], 所以我们只要不断更新dp[j]就行。那是否是在上述代码的基础上将递推方程由 dp[i] [j]max(dp[i−1] [j],dp[i−1] [j−w[i]]v[i])改为dp[j] max(dp[j], dp[j-w[i]] v[i])就万事大吉了呢宝贝你显然是太天真了
我们再来捋一下如果我们用for(int j 1; j m; j)我们每次更新都是从低位开始的并且后续的递推要用到前面的结论那我们来举例一下
如果有3个物品他们的花费和价值是
W: 1 2 3
V: 2 1 3
对于容量为5的背包
i1时
dp[1]2, dp[2] 4, dp[3] 6, dp[4] 8, dp[5] 10 有没有发现端倪为毛我这次的修改全体现到之后的更新上了这不对吧按我们的设想因该是i2的那次才会应用上才对但是这在完全背包问题中会被用到
我们换倒序一下for(int j m; j 0; j--)
i1时
dp[5] 2, dp[4] 2, dp[3] 2, dp[2] 2, dp[1] 2;
i2时
dp[5] 3, dp[4] 3, d[3] 3, dp[2] 2, dp[1] 2
i3时
dp[5] 5, dp[4] 5, d[3] 3, dp[2] 2, dp[1] 2
这不就全对上了嘛所以倒序可以避免这次的修改影响这次其它容量时的更新
代码如下
已知w[]和v[]
int[] dp new int[m 1]for(int i 1; i n; i) {//遍历物品注意下标的对应关系这里都假设物品从下标1开始记录for(int j m; j 0; j--) {//遍历容量dp[j] Math.max(dp[j], dp[j-w[i]] v[i]); }
}
还有个无伤大雅的小优化for(int j m; j w[i]; j--), 因为你剩余的空间如果都放不下这个物体了那这个物体的价值自然不会对答案产生影响并且后续的遍历中也不存在能放得下这个物体的情况可以直接跳过
已知w[]和v[]
int[] dp new int[m 1]for(int i 1; i n; i) {//遍历物品注意下标的对应关系这里都假设物品从下标1开始记录for(int j m; j w[i]; j--) {//遍历容量dp[j] Math.max(dp[j], dp[j-w[i]] v[i]); }
}
完全背包问题
问题描述 与0/1背包问题类似但每个物品可以无限次选择。
特点 每个物品可以被选择多次。
解决方案 动态规划同样使用动态规划但是状态转移方程有所不同因为物品可以被重复选择 dp[j]max(dp[j],dp[j−w[i]]v[i]) , dp[j]max(dp[j],dp[j−w[i]]v[i])其中对于每个物品我们尝试多次放入背包直到背包容量不足以再放入该物品为止。
代码
已知w[]和v[]
int[] dp new int[m 1]for(int i 1; i n; i) {//遍历物品注意下标的对应关系这里都假设物品从下标1开始记录for(int j 1; j w; j) {//遍历容量if(j w[i])dp[j] Math.max(dp[j], dp[j-w[i]] v[i]); }
}
