菜鸟都能理解的0-1背包问题的空间优化 如果你不知道什么叫做0-1背包问题，下面是0-1背包问题的简单描述
假设有n件物品
每件物品的体积为w1, w2……wn
相对应的价值为 v1, v2.……vn。

01背包是在n件物品取出若干件放在空间为total_weight的背包里，使得背包的总体积最大

关于0-1背包问题没有优化版本，请看

#include #define MAX_NUM 5 #define MAX_WEIGHT 10 using namespace std; //动态规划求解 int zero_one_pack(int total_weight, int w[], int v[], int flag[], int n) { int c[MAX_NUM+1][MAX_WEIGHT+1] = {0}; //c[i][j]表示前i个物体放入容量为j的背包获得的最大价值 // 状态转移方程：c[i][j] = max{c[i-1][j], c[i-1][j-w[i]]+v[i]} //状态转移方程的解释：第i件物品要么放，要么不放 //如果第i件物品不放的话,就相当于求前i-1件物体放入容量为j的背包获得的最大价值 //如果第i件物品放进去的话,就相当于求前i-1件物体放入容量为j-w[i]的背包获得的最大价值 for (int i = 1; i <= n; i++) { for (int j = 1; j <= total_weight; j++) { if (w[i] > j) { // 说明第i件物品大于背包的重量，放不进去 c[i][j] = c[i-1][j]; } else { //说明第i件物品的重量小于背包的重量，所以可以选择第i件物品放还是不放 if (c[i-1][j] > v[i]+c[i-1][j-w[i]]) { c[i][j] = c[i-1][j]; } else { c[i][j] =v[i] + c[i-1][j-w[i]]; } } } }//下面求解哪个物品应该放进背包 int i = n, j = total_weight; while (c[i][j] != 0) { if (c[i-1][j-w[i]]+v[i] == c[i][j]) { // 如果第i个物体在背包，那么显然去掉这个物品之后，前面i-1个物体在重量为j-w[i]的背包下价值是最大的 flag[i] = 1; j -= w[i]; //--i; 移到外面去 }--i; } return c[n][total_weight]; }int main() { int total_weight = 10; int w[4] = {0, 3, 4, 5}; int v[4] = {0, 4, 5, 6}; int flag[4]; //flag[i][j]表示在容量为j的时候是否将第i件物品放入背包 int total_value = https://www.it610.com/article/zero_one_pack(total_weight, w, v, flag, 3); cout <<"需要放入的物品如下" << endl; for (int i = 1; i <= 3; i++) { if (flag[i] == 1) cout << i << "重量为" << w[i] << ", 价值为" << v[i] << endl; } cout << "总的价值为: " << total_value << endl; return 0; } #include #define MAX_NUM 5 #define MAX_WEIGHT 10 using namespace std; //动态规划求解 int zero_one_pack(int total_weight, int w[], int v[], int flag[], int n) { int c[MAX_NUM+1][MAX_WEIGHT+1] = {0}; //c[i][j]表示前i个物体放入容量为j的背包获得的最大价值 // 状态转移方程：c[i][j] = max{c[i-1][j], c[i-1][j-w[i]]+v[i]} //状态转移方程的解释：第i件物品要么放，要么不放 //如果第i件物品不放的话,就相当于求前i-1件物体放入容量为j的背包获得的最大价值 //如果第i件物品放进去的话,就相当于求前i-1件物体放入容量为j-w[i]的背包获得的最大价值 for (int i = 1; i <= n; i++) { for (int j = 1; j <= total_weight; j++) { if (w[i] > j) { // 说明第i件物品大于背包的重量，放不进去 c[i][j] = c[i-1][j]; } else { //说明第i件物品的重量小于背包的重量，所以可以选择第i件物品放还是不放 if (c[i-1][j] > v[i]+c[i-1][j-w[i]]) { c[i][j] = c[i-1][j]; } else { c[i][j] =v[i] + c[i-1][j-w[i]]; } } } }//下面求解哪个物品应该放进背包 int i = n, j = total_weight; while (c[i][j] != 0) { if (c[i-1][j-w[i]]+v[i] == c[i][j]) { // 如果第i个物体在背包，那么显然去掉这个物品之后，前面i-1个物体在重量为j-w[i]的背包下价值是最大的 flag[i] = 1; j -= w[i]; //--i; 移到外面去 }--i; } return c[n][total_weight]; }int main() { int total_weight = 10; int w[4] = {0, 3, 4, 5}; int v[4] = {0, 4, 5, 6}; int flag[4]; //flag[i][j]表示在容量为j的时候是否将第i件物品放入背包 int total_value = https://www.it610.com/article/zero_one_pack(total_weight, w, v, flag, 3); cout <<"需要放入的物品如下" << endl; for (int i = 1; i <= 3; i++) { if (flag[i] == 1) cout << i << "重量为" << w[i] << ", 价值为" << v[i] << endl; } cout << "总的价值为: " << total_value << endl; return 0; }

上面的核心代码是下面这一段

for (int i = 1; i <= n; i++) { for (int j = 1; j <= total_weight; j++) { if (w[i] > j) { c[i][j] = c[i-1][j]; } else { if (c[i-1][j] > v[i]+c[i-1][j-w[i]]) { c[i][j] = c[i-1][j]; } else { c[i][j] =v[i] + c[i-1][j-w[i]]; } } } }

注意到状态转移方程 c[i][j] = max{c[i-1][j], c[i-1][j-w[i]]+v[i]}

每一次c[i][j]改变的值只与c[i-1][x] {x:1...j}【我的理解：x是范围是 1 到j】
有关c[i-1][x]是前一次i循环保存下来的值，
因此，可以将c缩减成一维数组
状态转移方程转换为 c[j] = max(c[j], c[j-w[i]]+v[i]);
并且，我们注意到状态转移方程， 每一次推导c[i][j]是通过c[i-1][j-w[i]]来推导的，而不是通过c[i][j-w[i]]
因此，j的 扫描顺序应该改成从大到小
否则，第i次求c数组，必然先求的c[j-w[i]]的值(即c[i][j-w[i]])，再求c[j](即c[i][j])的值
由于j递增,那么状态方程就成为下面这个样子了
c[i][j] = max(c[i-1][j], c[i][j-w[i]]+v[i])显然不符合题意


【我的理解：每一次推导c[i][j]是通过c[i-1][j-w[i]]来推导的，
意思是 在 j 容量下放i 与不放i ,那个价值比较大。
c[i-1][j-w[i]]表示在j的容积下准备放 i 物品】

j的扫描顺序应该改成从大到小，


所以，上面的代码变为






for (int i = 1; i <= n; i++) {
for (int j = total_weight; j >= 1; j--) {
if (w[i] > j) {
c[j] = c[j]; //表示第i次与第i-1次相等，这里因为c[j]本来就保存这上一次的值，所以这里不需变化
//而二维数组的写法是 c[ i ] [ j ] = c [ i-1 ] [ j ] ; 保存上一次的值
} else {
//说明第i件物品的重量小于背包的重量，所以可以选择第i件物品放还是不放
if (c[j] > v[i]+c[j-w[i]]) {// 二维数组：if (c[i-1][j] > v[i]+c[i-1][j-w[i]])
c[j] = c[j]; // 二维数组：c[i][j] = c[i-1][j]; 不放入 i
}
else {
c[j] =v[i] + c[j-w[i]]; //二维数组：c[i][j] = v[i] + c[i-1][j-w[i]]; 放入i
}
}
}
}

【我的理解：c[ j - w[i] ]与c[i-1][ j-w[i] ]的区别是：
首先是 "j"，前者是处理逆容量，后者是处理当前容量。
后者表示当前容量下放入i 前i的价值(value)，前者表示逆容量 - i的容量(费用)的价值
后者 + v[i],前者 + v[i],两个都加上i的价值，
然后
后者：【当前容量下放入i 前i的价值(value)】 + v[i]【i的价值】 与【当前容量的不放入i的价值】【 compare 】
c[i-1][j] 与 v[i]+c[i-1][j-w[i]] 比较
前者：【逆容量 - i占用的容量(费用)最后在此基础上得出的价值】+ v[i]【i的价值】 与【逆容量的价值】 【 compare 】
c[j]与 v[i]+c[j-w[i]]比较（意思是假设逆容量不包括i占用容量的时候的价值，这样再加上i的价值，这个时候再与 逆容量的价值 比较，
如果 小于的话，表示不放入i 更有价值；如果大于的话，表示放入i 更有价值。）

c[j] -v[i] > c[j-w[i]]放入i,说明容量不匹配，说明c[j] 价值很大，反之当前容量的价值很小

一个逆的比较，一个是顺的比较，两者的目的是一样的，都是为了绝对放不放i, 但是又有区别，区别在空间上发生了变化，实现
同样目标尝试逆的方法和顺的方法，可以发现有不同的效果。

】





最后我们可以做下优化，把不必要的语句去掉即可完成优化

for (int i = 1; i <= n; i++) for (int j = total_weight; j >= w[i]; j--) if (c[j] <= v[i] + c[j-w[i]]) c[j] = v[i] + c[j-w[i]];

如此优美的代码简直无法想象!
注意，
空间优化版本最后是求解不出来最优解序列的，
但是能求出最优解，也就是最大价值




背包01 问题的 二维数组 和 空间优化后一维数组 的实现

// //main.cpp //oneOfbag01 // //Created by 瑛峰 on 14/12/22. //Copyright (c) 2014年 angran. All rights reserved. //#include /** #define MAX_NUM 5 #define MAX_WEIGHT 10 using namespace std; //动态规划求解 int zero_one_pack(int total_weight, int w[], int v[], int flag[], int n) { int c[MAX_NUM+1][MAX_WEIGHT+1] = {0}; //c[i][j]表示前i个物体放入容量为j的背包获得的最大价值 // 状态转移方程：c[i][j] = max{c[i-1][j], c[i-1][j-w[i]]+v[i]} //状态转移方程的解释：第i件物品要么放，要么不放 //如果第i件物品不放的话,就相当于求前i-1件物体放入容量为j的背包获得的最大价值 //如果第i件物品放进去的话,就相当于求前i-1件物体放入容量为j-w[i]的背包获得的最大价值 for (int i = 1; i <= n; i++) {std::cout <<"\n\n"; for (int j = 1; j <= total_weight; j++) { if (w[i] > j) { // 说明第i件物品大于背包的重量，放不进去 c[i][j] = c[i-1][j]; } else { //说明第i件物品的重量小于背包的重量，所以可以选择第i件物品放还是不放 if (c[i-1][j] > v[i]+c[i-1][j-w[i]]) { c[i][j] = c[i-1][j]; } else { c[i][j] =v[i] + c[i-1][j-w[i]]; } }std::cout << "c["<= 1; j--) { if (w[i] > j) { c[j] = c[j]; //表示第i次与第i-1次相等，这里因为c[j]本来就保存这上一次的值，所以这里不需变化 } else { //说明第i件物品的重量小于背包的重量，所以可以选择第i件物品放还是不放 if (c[j] > v[i]+c[j-w[i]]) { c[j] = c[j]; } else { c[j] =v[i] + c[j-w[i]]; } } std::cout << "c["<

空间优化的输出 c[10]的值4
c[9]的值4
c[8]的值4
c[7]的值4
c[6]的值4
c[5]的值4
c[4]的值4
c[3]的值4
c[2]的值0
c[1]的值0




c[10]的值9
c[9]的值9
c[8]的值9
c[7]的值9
c[6]的值5
c[5]的值5
c[4]的值5
c[3]的值4
c[2]的值0
c[1]的值0




c[10]的值11
c[9]的值11
c[8]的值10
c[7]的值9
c[6]的值6
c[5]的值6
c[4]的值5
c[3]的值4
c[2]的值0
c[1]的值0
总的价值为: 11




------------------------
二维数组的 输出
c[1][1]的值0

c[1][2]的值0
c[1][3]的值4
c[1][4]的值4
c[1][5]的值4
c[1][6]的值4
c[1][7]的值4
c[1][8]的值4
c[1][9]的值4
c[1][10]的值4




c[2][1]的值0
c[2][2]的值0
c[2][3]的值4
c[2][4]的值5
c[2][5]的值5
c[2][6]的值5
c[2][7]的值9
c[2][8]的值9
c[2][9]的值9
c[2][10]的值9




c[3][1]的值0
c[3][2]的值0
c[3][3]的值4
c[3][4]的值5
c[3][5]的值6
c[3][6]的值6
c[3][7]的值9
c[3][8]的值10
c[3][9]的值11
c[3][10]的值11
需要放入的物品如下
flag[1]的值32767
flag[2]的值1
2重量为4,价值为5
flag[3]的值1
3重量为5,价值为6
总的价值为: 11


--------------------------------------------
观察其特征： 结果其实是一样的，只不过 一维数组是倒着输出。！









【算法(algorithm)|背包问题再理解】

推荐阅读

• 

  智能分析平台
• 

  商标公证处 商标公证书怎么办理，商标公证书
• 

  恶意诉讼罪如何报案
• 

  内衣发霉了还能不能穿 运动内衣发霉了还能穿吗
• 

  信用卡欠款低于5万不予立案是真的吗
• 

  如何注册一仟金融 注册一仟金融的具体方法
• 

  一张稿纸的命运|一张稿纸的命运 作者（刘德源（赵云）一年级）
• 

  支付宝App申请防丢卡套的具体操作步骤
• 

  20岁怀孕打掉会伤身体吗 怎么算孕周期才是正确的
• 

  风湿性关节炎用什么泡脚好 风湿性关节炎用什么泡脚好得快
• 

  最快方法 识别脑中风
• 

  家庭清洁消毒杀菌用什么
• 

  经营现金流为负的原因分析 经营现金流为负的原因是什么
• 

  车厘子可以用盐水泡吗
• 

  怎样做娃娃菜
• 

  男人吃蛋白质粉可以吗？男人吃蛋白粉的好处
• 

  胃炎|胃酸嗳气胃胀痛，各型胃炎胃溃疡及胃气不舒，中医小窍门迅速解决
• 

  世界微笑日宣传语 世界微笑日是哪天
• 

  减肥喝酸奶的作用 酸奶有减肥的功效吗
• 

  面包糠变软了还能炸脆吗

• c++回顾|【c++回顾】3.1经典算法问题-0/1背包价值最大问题
• 背包问题小结