目录

证明最优子结构

​编辑

图解

递归关系

代码规整版（书上的代码就是函数前面加了book的）

老师那个vs6老六编译器，不支持变量定义数组大小版本

图解​编辑

图解（查找是否获取图解即traceback函数）

下面我用容积代表重量（我是不会承认我看走眼了的。又懒得改。）

0-1背包问题是动态规划背包问题系列的最基础的一个问题。

相对理解起来较为简单。

按书上来说，要证明一个问题是否可以使用动态规划思想，需要满足最优子结构的性质，那么什么是最优子结构的性质呢？

书上给出的定义如下图

看起来很拗口，其实就是不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。说白了就是一个最优策略的子策略也是必须是最优的，而所有子问题的局部最优解将导致整个问题的全局最优。如果一个问题能满足最优化原理，就称其具有最优子结构性质。这是判断问题能否使用动态规划解决的先决条件，如果一个问题不能满足最优化原理，那么这个问题就不适合用动态规划来求解。

但是如果感觉这个理解起来还是很困难，我们还有另一种方法进行判断，就是无后效性。

什么是无后效性呢，就是当前的决策只影响当前的状态不对后续的状态造成影响，而且与到底此状态的方式无关，说简单点就是当前状态所做的决策和选择不影响后续状态，也不受以前的状态影响。

证明最优子结构

书上给出的证明如下

如果觉得难以理解，接下来我会做出一定的解释。

现在清洗一下脑子，接下来是一段很奇怪的证明方式，我们将引入反证法。（按我的习惯来的，书上用的y，不太一样。）

首先我们假设(x1，x2，…，xn)是01背包问题的最优解，那么其中的每一个x都代表一个子问题的最优解，映射到题目中就是每个物品选择与否。那么则有(x2，x3，…，xn)是其子问题的最优解，现在我们又假设(y2，y3，…，yn)是上述问题的子问题最优解，那么则有

(v2 * y2+v3 * y3+…+vn * yn)+v1 * x1 > (v2 * x2+v3 * x3+…+vn * xn)+v1 * x1

说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理。（是不是感觉在鬼扯）

但是证明无后效性就显得很简单，对于任意一个阶段，只要背包剩余容量和可选物品是一样的，那么我们能做出的现阶段的最优选择必定是一样的，是不受之前选择了什么物品所影响的。即满足无后效性。

书上的递归关系我会在下面解释。

图解

这是我最不想弄的东西，因为非常的麻烦。

现在有这样一堆宝物（w代表体积，v代表价值）

那么这里我们就需要选择四次，使得x1 * 3 + x2 * 2 + x3 * 5 + x4 * 7 <c（c为背包总容量），使得价值最大。现在假设C为12

首先初始时我们的背包容量还是12，对宝物1只有两种状态，选择或者不选择。

然后依次对4个宝物进行选择就会得到下图。

图中选择宝物2有点弄反了，用软件自动调整了一下就这样了，将就看吧。

当然这个图是不太正确的，因为在选择宝物三因容积不够选择宝物四的时候就已经是结果了，但是我为了看着方便还是选择迁出一根线来表示，就是最后一行没有红线的所有框框，因为这样我们就把结果全部弄到最后一行了，便于观察。很明显最优的选择是价值为13背包容量为0的那个选择图，即为选择宝物1，2，4不选择宝物3的那条路。

好弄现在通过图像明白了流程，接下来我们就研究一下书上说的递归关系。

递归关系

书中所给为下图

这书可真垃圾，让我怀疑自己错了，再三求证才发现是书错了，差评，可见不能尽信书上所言。

这一部分呢其实就是分析咱们每一个状态的选择策略，只是用数学公式化了。

要理解这个需要用到编程的东西具象化。

数组表现形式如下图

书中内容是从左下角求到右上角。

现在有一个二维数组m [ i ] [ j ] ，i 代表的是每个宝物，j 代表的是背包的容积，m [ i ] [ j ]里面存储的就是当前背包内的宝物价值，w代表宝物的容积，v代表宝物的价值。

那么对于当前这个宝物还是只有两个状态，选择或者不选择。i +1是我们已经选择过的宝物，那么立足于当前状态的这个宝物，对于这个宝物的上一个宝物是不是就是 i + 1 所以上面会出现，m [ i+1 ] [ j ] 。

那么现在对于下一个宝物有两种选择（当然能选择肯定是背包的容积还大于宝物的体积的时候）。

不选择那么背包的状态不变，就是m [ i+1 ] [ j ]即上一个宝物的状态

选择，那么背包的状态肯定会变化，首先背包的容积发生改变，即 j 发生改变，该有背包内物品的价值发生改变，就是 m [ i ] [ j ] 内存储的值发生变化，就是m [ i + 1 ] [ j – w [ i ] ] + v [ i ]

那么对应当前的状态我们需要最佳，肯定是选择最大的那个啊。所以需要用max比较一下，看一下当前的状态哪个最好。

大概就是这样。动态规划最重要的就是递归公式，其实叫递推公式更形象。

代码后续更新。

代码规整版（书上的代码就是函数前面加了book的）

#include #include #include #include void myKnapsack(int *v,int *w,int n,int c);void traceback(int *w,int n,int c,int*m[n+1][c+1]);void bookKnapsack(int *v,int *w,int n,int c,int *m[n+1][c+1]);void booktraceback(int *w,int n,int c,int*m[n+1][c+1]);int max(int x,int y);int min(int x,int y);int main(){//int n;//printf("宝物数量");//scanf("%d",&n);//int w[n+1],v[n+1];//int c;//printf("背包总量");//scanf("%d",&c);//int i=0,j=0;//int m[n+1][c+1];//for(i=1;i<n+1;i++)//{//printf("请输入第%d个宝物的重量: ",i);//scanf("%d",&w[i]);//printf("请输入第%d个宝物的价值: ",i);//scanf("%d",&v[i]);//}//printf("\n");//for(i=0;i<n+1;i++)//{//if(i==0)//{//printf("w= ");//}//else//{//printf("%d ",w[i]);//}//}//printf("\n");//for(i=0;i<n+1;i++)//{//if(i==0)//{//printf("v= ");//}//else//{//printf("%d ",v[i]);//}//}//printf("\n");//printf("\n");//myKnapsack(v,w,n,c);//printf("\n");int n=4;int c=10;int w[]= {0,2,3,5,5};int v[]= {0,2,4,3,7};int i,j;printf("\n");myKnapsack(v,w,n,c);printf("\n");int m[n+1][c+1];bookKnapsack(v,w,n,c,m);}//这个函数思想和我的差不多，也是从最后结果开始查找void booktraceback(int *w,int n,int c,int*m[n+1][c+1]){int i,j;int x[n];for(i=1; i1; i--){//这里和上面那个jMax一样jMax = min(w[i]-1, c);//装不下就背包状态不变for (j = 0; j <= jMax; j++){m[i][j] = m[i + 1][j];}//能装下就进项判断之所以用(int)转换一下，是因为不转换电脑会算错，我也不知道为啥，应该是语言缺陷啥的for (j = w[i]; j = w[1]){m[1][c] = max(m[1][c], (int)m[2][c - w[1]]+v[1]);//根据价值决定到底装不装}printf("（书上的）遍历后数组为\n"); for(i=1; i<=n; i++){printf("\n");for(j=0; j<=c; j++){ printf("%-3d ",m[i][j]);}}printf("\n");printf("最大收益为 %d",m[1][c]);printf("\n");booktraceback(w,n,c,m);//调用查找函数}int min(int x,int y){if(xy)return y;elsereturn x;}int max(int x,int y){if(x>y)return x;else if(x=1; i--){if(m[i-1][c]!=m[i][c])//第i个物品被选中{choice[i]=1;c=c-w[i];//从m(i-1,j-wi)开始寻找}else if (m[i-1][c]=m[i][c])//第i个物品没有被选中{choice[i]=0;}}for(i=1; i<=n; i++){if(choice[i]==1){printf("第%d件宝物被选择\n",i);}else{printf("第%d件宝物未被选择\n",i);}}}void myKnapsack(int *v,int *w,int n,int c){int m[n+1][c+1];int i,j,tmp;for(i=0; i<=n; i++)//将数组的第0行0列全部初始化为0{m[i][0]=0;}for(i=0; i<=c; i++){m[0][i]=0;}for(i=1; i<=n; i++)//遍历数组开始寻找{for(j=1; j<=c; j++){if(jm[i-1][j-w[i]]+v[i])//利用递推公式判断是否将物品装进背包{m[i][j]=m[i-1][j];}else{m[i][j]=m[i-1][j-w[i]]+v[i];}}}}printf("（我的）遍历后矩阵为\n");for(i=1; i<=n; i++){for(j=1; j<=c; j++){printf("%-3d ",m[i][j]);}printf("\n");}printf("\n");printf("最大价值为%d\n",m[n][c]);printf("\n");traceback(w,n,c,m);}

老师那个vs6老六编译器，不支持变量定义数组大小版本

#include #include #include #include void myKnapsack(int *v,int *w,int n,int c,int m[5][11]);void traceback(int *w,int n,int c,int m[5][11]);void bookKnapsack(int *v,int *w,int n,int c,int m[5][11]);void booktraceback(int *w,int n,int c,int m[5][11]);int max(int x,int y);int min(int x,int y);int max(int x,int y);int min(int x,int y);void main(){int n=4;int c=10;int w[]= {0,2,3,5,5};int v[]= {0,2,4,3,7};int i=0,j=0;int m[5][11];myKnapsack(v,w,n,c,m);printf("\n");int bookm[5][11];bookKnapsack(v,w,n,c,bookm);}void traceback(int *w,int n,int c,int m[11][11]){int i=0;int choice[10];for(i=n; i>=1; i--){if(m[i-1][c]!=m[i][c])//第i个物品被选中{choice[i]=1;c=c-w[i];//从m(i-1,j-wi)开始寻找}else if (m[i-1][c]=m[i][c])//第i个物品没有被选中{choice[i]=0;}}for(i=1; i<=n; i++){if(choice[i]==1){printf("第%d件宝物被选择\n",i);}else{printf("第%d件宝物未被选择\n",i);}}}void myKnapsack(int *v,int *w,int n,int c,int m[5][11]){int i,j;for(i=0; i<=n; i++)//将数组的第0行0列全部初始化为0{m[i][0]=0;}for(i=0; i<=c; i++){m[0][i]=0;}for(i=1; i<=n; i++)//遍历数组开始寻找{for(j=1; j<=c; j++){if(jm[i-1][j-w[i]]+v[i])//利用递推公式判断是否将物品装进背包{m[i][j]=m[i-1][j];}else{m[i][j]=m[i-1][j-w[i]]+v[i];}}}}printf("（我的）遍历后矩阵为\n");for(i=1; i<=n; i++){for(j=1; j<=c; j++){printf("%-3d ",m[i][j]);}printf("\n");}printf("\n");printf("最大价值为%d\n",m[n][c]);printf("\n");traceback(w,n,c,m);}//这个函数思想和我的差不多，也是从最后结果开始查找void booktraceback(int *w,int n,int c,int m[5][11]){int i=0;int x[5];for(i=1; i<n; i++){if(m[i][c]==m[i+1][c]){x[i]=0;}else{x[i]=1;c -= w[i];}}x[n]=(m[n][c])?1:0;for(i=1; i<=n; i++){if(x[i]==1){printf("第%d件宝物被选择\n",i);}else{printf("第%d件宝物未被选择\n",i);}}}void bookKnapsack(int *v,int *w,int n,int c,int m[5][11]){//找出两个数中比较小的数为下面的模拟装宝物n做准备(就是初始化m数组)。//之所以减1是因为j代表的是背包容量，w[n]代表宝物所需容量，背包容量只需要比宝物容量减1大即可。int jMax = min(w[n] - 1, c);int i,j;//初始化m数组，要是不初始化，后面打印数组时会打印地址出来for(i=0; i<=n; i++){for(j=0; j<=c; j++){ m[i][j]=-1;}}//这里是模拟装宝物n，如果当前背包容量比宝物n所需容量即装不进背包，顾背包内价值为0for (j = 0; j<=jMax; j++){m[n][j] = 0;}//这里是装的下宝物n的时候，就装下，背包内价值为v[n]for (j = w[n]; j 1; i--){//这里和上面那个jMax一样jMax = min(w[i]-1, c);//装不下就背包状态不变for (j = 0; j <= jMax; j++){m[i][j] = m[i + 1][j];}//能装下就进项判断之所以用(int)转换一下，是因为不转换电脑会算错，我也不知道为啥，应该是语言缺陷啥的for (j = w[i]; j = w[1]){m[1][c] = max(m[1][c], (int)m[2][c - w[1]]+v[1]);//根据价值决定到底装不装}printf("（书上的）遍历后数组为\n"); for(i=1; i<=n; i++){printf("\n");for(j=0; j<=c; j++){ printf("%-3d ",m[i][j]);}}printf("\n");printf("最大收益为 %d",m[1][c]);printf("\n");booktraceback(w,n,c,m);//调用查找函数}int min(int x,int y){if(xy)return y;elsereturn x;}int max(int x,int y){if(x>y)return x;else if(x<y)return y;elsereturn x;}

图解

图解（查找是否获取图解即traceback函数）

下面有解释

图中标黄部分为所利用到的点，根据咱们的递推原理，进行反推其实就能得到哪些宝物被选择，首先从坐标(4,12)开始，就是最后的答案处即（n,c）开始查找(n为宝物个数)，如果m（i-1，j）=m（i，j）就说明这个物品没有被选择，那么就需要从m（i-1，j）继续寻找，如果m（i-1，j）!=m（i，j）就说明该物品被选择了，就需要从m（i-1，j-w[i]）开始寻找，这里的 i 的含义为第几个宝物。

举个栗子 i= 4，从m[ 4 ][ 12 ]开始寻找m[ 3 ][ 12 ] !=m[ 4 ][ 12 ] 所以宝物4被选择了，接下来需要来到m[ 4 – 1 ] [ c- w[ i ]]即m[ 4-1 ] [ 12 – 7 ] = m[ 3 ] [ 5 ] 开始寻找。

此时m[ 3 ] [ 5 ] = m [ 2 ] [ 5 ] 所以宝物3没有被选择，就需要从 m [ 2 ] [ 5 ] 开始寻找。