动态规划-(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("最大价值为%dn",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("最大价值为%dn",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 ] 开始寻找。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>