动态规划-（0-1）背包问题_0-1背包问题

目录

证明最优子结构

​编辑

图解

递归关系

代码规整版（书上的代码就是函数前面加了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 <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
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 <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
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 ] 开始寻找。