C++之背包DP问题

写在前面背包DP是普及组比较重要的算法之一用于解决贪心解决不了的问题先看题描述一个旅行者有一个最多能装 M 公斤的背包现在有 n 件物品它们的重量分别是 W1​,W2​,...,Wn​,它们的价值分别为 C1​,C2​,...,Cn​求旅行者能获得最大总价值。输入描述第 1 行两个整数M 背包容量M≤200 和 N ( 物品数量N≤30 )。第 2…N1 行每行二个整数 Wi​,Ci​表示每个物品的重量和价值。输出描述仅一行一个数表示最大总价值。样例输入 110 4 2 1 3 3 4 5 7 9样例输出 112提示M≤200N≤30分析先尝试暴力枚举每一个物品要或不要需要θ2^30显然会出现 time limit exceed 的问题。怎么办众所周知一般地背包容量越大在物体价值、重量一定的情况下背包容量越大理论上总价值越大。那么我们可不可以声明一个数组dp[2009]使dp[i]表示容积为i时的最大价值试试就逝世试试for (int i 1; i n; i) { for (int j m; j w[i]; j--) {//01背包因为物品只有一件不能重复选择每个数据在上一轮的基础上产生 dp[j] max(dp[j], c[i] dp[j - w[i]]); } }恭喜你发明了01背包算法该算法的状态转移方程一般为dp[j] max(dp[j], c[i] dp[j - w[i]]);再看第二道题描述设有 n 种物品每种物品有一个重量及一个价值。但每种物品的数量是无限的同时有一个背包最大载重量为 M今从 n 种物品中选取若干件(同一种物品可以多次选取)使其重量的和小于等于 M而价值的和为最大。输入描述第一行两个整数M ( 背包载重M≤200 )和 N ( 物品数量N≤30 )。第 2…N1 行每行二个整数 Wi​,Ci​表示每个物品的重量和价值。输出描述仅一行一个数表示最大总价值。样例输入 110 4 2 1 7 9 1 1 4 5样例输出 112提示M≤200N≤30分析两道题唯一的区别在于是否可以“重复选取”。如果我们还用01背包问题的状态转移方程再这样的样例中就会错得非常离谱样例输入 样例输出 10 4 10000000 54188 1 114514 1 396396 1 1 1000000我们的答案将会为1000000与标准答案差得很远。有同学说这好办啊把01背包加一层while不就行了吗确实针对本题可行但是如果数据量变成类似1≤m,n≤5*10^7且m*n≤5*10^7就不可行了。那么又有同学说把上一题中内层循环从倒序改为顺序不就行了吗于是for (int i 1; i n; i) { for (int j w[i]; j m; j) { dp[j] max(dp[j], c[i] dp[j - w[i]]); } }恭喜你发明了完全背包算法该算法的状态转移方程依旧为dp[j] max(dp[j], c[i] dp[j - w[i]]);但是变成顺序循环最后看一道题描述有 N 种物品和一个容量是 M 的背包。第 i 种物品最多有 si 件每件体积是 wi价值是 ci。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入描述第一行两个整数NM用空格隔开分别表示物品种数和背包容积。接下来有 N 行每行三个整数 wi,ci,si用空格隔开分别表示第 i 种物品的体积、价值和数量。输出描述输出一个整数表示最大价值。样例输入 14 5 1 2 3 2 4 1 3 4 3 4 5 2样例输出 110提示0N≤50000M≤50000ci,wi,si≤5000分析有同学说这好办啊把01背包加一层for不就行了吗但是本题数据显然不允许这样的操作学过《人教版物理八年级上册》中用托盘天平测量质量这一课的同学或许会想到老师上课问的一个问题为什么砝码质量分别为500g,200g,200g,100g,50g,20g,20g,10g游码质量为0~5.0g原因很简单用这些可以组成0~1105.0g中间的任何一种情况保留一位小数。那么如果将这类背包算法进行如下改动是不是就可以了呢int a[n * 30], b[n * 30], q 0; // 注意大数组建议开在全局中 for (int i 1; i n; i) { for (int j 1; ((j 1) - 1) * w[i] m ((j 1) - 1) s[i]; j 1) { a[q] j * c[i]; b[q] j * w[i]; if ((j 1) - 1 s[i]) { a[q] (s[i] 1 - (j 1)) * c[i]; b[q] (s[i] 1 - (j 1)) * w[i]; } } }然后再进行for (int i 1; i q; i) { for (int j m; j b[i]; j--) { dp[j] max(dp[j], dp[j - b[i]] a[i]); } }恭喜你又发明了多重背包算法其状态转移方程为dp[j] max(dp[j], dp[j - b[i]] a[i]);写在最后/声明文章为本蒟蒻原创欢迎各位dalao点赞收藏并提出您宝贵的建议