0-1背包问题-动态规划

2022-08-21 09:07:33

问题描述

 给定n个物品和一个背包。物品i的重量为wi,价值为vi,背包容量为c。

如何选择装入背包中的物品,使得装入背包的物品的价值最大?

 每种物品i只有两种选择,装入或者不装入,既不能装入多次,也不能只装入一部分。
 此问题称为0-1背包问题。


问题形式化描述

 问题的形式描述是:给定c>0, w i w_iwi>0, v i v_ivi>0,1≤i≤n,求n元0-1向量( x 1 x_1x1, x 2 x_2x2, …, x n x_nxn),使得
 (物品i的重量为wi,价值为vi,背包容量为c。)
在这里插入图片描述

最优子结构性质

 设( y 1 y_1y1, y 2 y_2y2, …, y n y_nyn)是所给0-1背包问题的一个最优解,则( y 2 y_2y2, …, y n y_nyn)是下面子问题的最优解:
在这里插入图片描述

 反之,假如( y 2 y_2y2, …, y n y_nyn)不是上面子问题最优解,则设( z 2 z_2z2, …, z n z_nzn)是该子问题最优解,则( y 1 y_1y1, y 2 y_2y2, …, y n y_nyn)是原问题的最优解,而( y 1 y_1y1, y 2 y_2y2, …, y n y_nyn)不是原最优解。矛盾
在这里插入图片描述

 设( z 2 z_2z2, …, z n z_nzn)是该子问题最优解,( y 2 y_2y2, …, y n y_nyn)不是上面子问题最优解
在这里插入图片描述
 因此, ( y 1 y_1y1, z 2 z_2z2, …, z n z_nzn)所给0-1背包问题的一个最优解,而( y 1 y_1y1, …, y n y_nyn)不是原0-1背包问题的一个最优解,矛盾,因此( z 2 z_2z2, …, z n z_nzn)不是上述子问题的一个最优解, ( y 2 y_2y2, …, y n y_nyn) 是子问题最优解,最优子结构性质成立。


0-1背包问题的递归式

从第n个物品开始依次向前装,装的顺序为:
           (n, n-1, n-2, …, i+1, i, i-1, …, 1)
 m(i, j):当前背包容量为j,选择物品为n, n-1, n-2, …, i+1, i 装入背包产 生的价值

 寻找递推关系式,面对当前商品i有两种可能性:

  1. 包的容量比商品i体积小,装不下,此时的价值与前n-i个的价值是一样的,即m(i,j)=m(i+1,j)
  2. 还有足够的容量可以装该商品i,但装了也不一定达到当前最优价值,所以在装与不装之间选择最优的一个,即m(i,j)=max{ m(i+1, j),m(i+1,j-wi)+vi }

其中m(i+1,j)表示不装i的价值,m(i+1,j-wi)+vi 表示装了第i个商品,背包容量减少w(i), 但价值增加了v(i);

 由此可以得出递推关系式
在这里插入图片描述


算法描述

  • 用二维数组m[i][j], 0≤j≤c, 来存储m(i, j)的值。

  • 求解0-1背包问题就是在二维数组m中填入相应的值。

  • m[1][c]中的值就是该背包问题的解

  • 在二维数组m中最先填入的应该是哪些呢?

     二维数组m中最先填入物品n的最优解m(n, j):

    • 若0≤j< w n w_nwn,m[n][j]=0;
    • 若j≥ w n w_nwn,m[n][j]= v n v_nvn

例子

在这里插入图片描述
 根据递推关系式得到表中数据:
在这里插入图片描述
构造最优解(x1,x2,…,xn)算法:

  如果m[1][c]=m[2][c], 则x1=0, 否则x1=1;
     如果x1=0, 则由m[2][c]构造解;
     如果x1=1, 则由m[2][c-w1]构造解;
  依次类推,可构造出相应的最优解:(x1,x2,…,xn)

上述例子最优解: (x1,x2, x3, x4)=(1,0,1,1)


核心算法

在这里插入图片描述

voidKnapsack(int v[],int w[],int c,int n,int m[][10]){int jMax=min(w[n]-1,c);//背包剩余容量上限 范围[0~w[n]-1]for(int j=0; j<=jMax;j++){  
        m[n][j]=0;}for(int j=w[n]; j<=c; j++)//限制范围[w[n]~c]{  
        m[n][j]= v[n];}for(int i=n-1; i>1; i--){  
        jMax=min(w[i]-1,c);for(int j=0; j<=jMax; j++)//背包不同剩余容量j<=jMax<c{  
            m[i][j]= m[i+1][j];//没产生任何效益}for(int j=w[i]; j<=c; j++)//背包不同剩余容量j-wi >c{  
            m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//效益值增长vi}}  
    m[1][c]= m[2][c];if(c>=w[1]){  
        m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}}

在这里插入图片描述
最优求解算法Traceback

//x[]数组存储对应物品0-1向量,0不装入背包,1表示装入背包voidTraceback(int m[][10],int w[],int c,int n,int x[]){for(int 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;}

0-1背包问题的阶跃性

 但是,但是!!该算法有两个明显的缺点:
   1. 基于上述代码,因为数组索引的需要,要求所给物品重量为整数。
   2. 当背包容量C很大时,算法所需计算时间较多。当C>2n时,需要Ω(n*2n)计算时间。

 所以,所以!!改进算法如下:

 对于函数m(i,j)的值,当i确定,j为自变量时,是单调不减的跳跃式增长,如图所示。而这些跳跃点取决于在(物品i,物品i+1,……物品n)中选择放入哪些物品使得在放入重量小于容量 j (0<=j<=C)的情况下m取得最大值。对于每一个确定的i值,都有一个对应的跳跃点集Pi={ ( j, m(i,j) ),……}。j始终小于等于C

img

 (1)开始求解时,先求Pi,初始时Pn+1={(0,0)},i=n+1,由此按下列步骤计算Pi-1,Pi-2……P1,即Pn,Pn-1,……P1

 (2)求Qi,利用Pi求出m(i,j-w[i-1])+v[i-1],即Pi当放入物品i-1后的变化后的跳跃点集Qi={ ( j+w[i-1], m(i,j)+v[i-1] ),……},在函数图像上表现为所有跳跃点横轴坐标右移w[i-1],纵轴坐标上移v[i-1]。

 (3)求Pi-1,即求Pi∪Qi然后再去掉受控跳跃点后的点集。此处有个受控跳跃点的概念:若点(a,b),(c,d)∈Pi∪Qi,且a<=c,b>d,则(c,d)受控于(a,b),所以(c,d)∉Pi-1。去掉受控跳跃点,是为了求得在物品i-1放入后m较大的点,即 使m取最优值的跳跃点。

 由此计算得出Pn,Pn-1,……,P1。求得P1的最后那个跳跃点即为所求的最优值m(1,C)。


例子

 n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}。跳跃点的计算过程如下:


 初始时p[6]={(0,0)}

 因此,q[6]=p[6]⊕(w[5],v[5])={(4,6)}


 p[5]={(0,0),(4,6)}

 q[5]=p[5]⊕(w[4],v[4])={(5,4),(9,10)}


 p[4]={(0,0),(4,6),(9,10)}p[5]与q[5]的并集p[5]∪q[5]={(0,0),(4,6),(5,4),(9,10)}中跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后,得到p[4]

 q[4]=p[4]⊕(6,5)={(6,5),(10,11)}


 p[3]={(0,0),(4,6),(9,10),(10,11)}

 q[3]=p[3]⊕(2,3)={(2,3),(6,9)}


 p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}

 q[2]=p[2]⊕(2,6)={(2,6),(4,9),(6,12),(8,15)}


 p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)}


p[1]的最后的那个跳跃点(8,15)即为所求的最优值,m(1,C)=15



完整代码

#include<bits/stdc++.h>
using namespace std;constint MAX=1024;int n;//物品个数int c;//包的容量int value[MAX];//物品的价值int weight[MAX];//物品的重量int x[MAX];//n元0-1向量int m[MAX][MAX];//解的容器voidInput(){
    cout<<"请先输入物品个数和包的容量(n c):";
    cin>>n>>c;
    cout<<"请输入每件物品的重量和价值(v w):"<<endl;for(int i=1; i<= n;++i)
        cin>>value[i]>>weight[i];}//创建最优解voidKnapsack(){memset(m,0,sizeof(m));for(int i=1; i<= n;++i)//逐行填表,i表示当前可选物品数,j表示当前背包的容量, 也就是从低到顶。{for(int j=1; j<= c;++j){if(j< weight[i])
                m[i][j]= m[i-1][j];else{
                m[i][j]=max(m[i-1][j], m[i-1][j- weight[i]]+ value[i]);}}}}//获取最优解(即设法将求得的最优解输出出来)voidTraceback(){int cc= c;for(int i= n; i>1;--i){if(m[i][cc]== m[i-1][cc])
            x[i]=0;else{
           x[i]=1;</
  • 作者:迷雾总会解
  • 原文链接:https://blog.csdn.net/qq_44766883/article/details/107085189
    更新时间:2022-08-21 09:07:33