目录
证明最优子结构
编辑
图解
递归关系
代码规整版（书上的代码就是函数前面加了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; 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[n+1][c+1])
{
// 找出两个数中比较小的数为下面的模拟装宝物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所需容量即装不进背包，顾背包内价值为0
for (j = 0; j<=jMax; j++)
{
m[n][j] = 0;
}
// 这里是装的下宝物n的时候，就装下，背包内价值为v[n]
for (j = w[n]; j <= c; j++)
{
m[n][j] = v[n];
}
// 因为宝物n已经装了,就只需要从n-1 求到2即可,最后一步后面模拟(我也不理解为什么这样,本来直接像我写的代码一直算就行了)
for (i = n -1; i>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 <= c; j++)
{
m[i][j] = max(m[i + 1][j], (int)m[i + 1][j - w[i]]+v[i]);//当前背包容量装得下，但是要判断其价值是否最大，确定到底装不装
}
}
// 这里开始模拟最后一个宝物1的过程
m[1][c] = m[2][c];//先假设1物品不装
if (c >= 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(x<y)
return x;
else if(x>y)
return y;
else
return x;
}
int max(int x,int y)
{
if(x>y)
return x;
else if(x<y)
return y;
else
return x;
}
void traceback(int *w,int n,int c,int*m[n+1][c+1])
{
int i,j;
int choice[n];
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[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(j<w[i])//当背包容积小于当前物品重量时背包状态不变
{
m[i][j]=m[i-1][j];
}
else
{
if(m[i-1][j]>m[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(j<w[i])//当背包容积小于当前物品重量时背包状态不变
{
m[i][j]=m[i-1][j];
}
else
{
if(m[i-1][j]>m[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所需容量即装不进背包，顾背包内价值为0
for (j = 0; j<=jMax; j++)
{
m[n][j] = 0;
}
// 这里是装的下宝物n的时候，就装下，背包内价值为v[n]
for (j = w[n]; j <= c; j++)
{
m[n][j] = v[n];
}
// 因为宝物n已经装了,就只需要从n-1 求到2即可,最后一步后面模拟(我也不理解为什么这样,本来直接像我写的代码一直算就行了)
for (i = n -1; i>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 <= c; j++)
{
m[i][j] = max(m[i + 1][j], (int)m[i + 1][j - w[i]]+v[i]);//当前背包容量装得下，但是要判断其价值是否最大，确定到底装不装
}
}
// 这里开始模拟最后一个宝物1的过程
m[1][c] = m[2][c];//先假设1物品不装
if (c >= 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(x<y)
return x;
else if(x>y)
return y;
else
return x;
}
int max(int x,int y)
{
if(x>y)
return x;
else if(x<y)
return y;
else
return 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 ] 开始寻找。