菜鸟都能理解的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)|背包问题再理解】
