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

问题描述给定n个物品和一个背包。物品i的重量为wi，价值为vi，背包容量为c。如何选择装入背包中的物品，使得装入背包的物品的价值最大？每种物品i只有两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。此问题称为0-1背包问题。问题形式化描述问题的形式描述是：给定c＞0，wiw_iwi＞0，viv_ivi＞0，1≤i≤n，求n元0-1向量(x1x_1x1, x2x_2x2

迷雾总会解

5705人浏览 · 2020-07-02 16:10:27

迷雾总会解 · 2020-07-02 16:10:27 发布

问题描述

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

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

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

问题形式化描述

问题的形式描述是：给定c＞0， $w_i$ ＞0， $v_i$ ＞0，1≤i≤n，求n元0-1向量( $x_1$ , $x_2$ , …, $x_n$ )，使得
(物品i的重量为wi，价值为vi，背包容量为c。)
在这里插入图片描述

最优子结构性质

设( $y_1$ , $y_2$ , …, $y_n$ )是所给0-1背包问题的一个最优解，则( $y_2$ , …, $y_n$ )是下面子问题的最优解：
在这里插入图片描述

反之，假如( $y_2$ , …, $y_n$ )不是上面子问题最优解，则设( $z_2$ , …, $z_n$ )是该子问题最优解，则( $y_1$ , $y_2$ , …, $y_n$ )是原问题的最优解，而( $y_1$ , $y_2$ , …, $y_n$ )不是原最优解。矛盾。
在这里插入图片描述

设( $z_2$ , …, $z_n$ )是该子问题最优解,( $y_2$ , …, $y_n$ )不是上面子问题最优解
在这里插入图片描述
因此， ( $y_1$ , $z_2$ , …, $z_n$ )所给0-1背包问题的一个最优解，而( $y_1$ , …, $y_n$ )不是原0-1背包问题的一个最优解，矛盾，因此( $z_2$ , …, $z_n$ )不是上述子问题的一个最优解， ( $y_2$ , …, $y_n$ ) 是子问题最优解，最优子结构性质成立。

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有两种可能性：

包的容量比商品i体积小，装不下，此时的价值与前n-i个的价值是一样的，即m(i,j)=m(i+1,j)；
还有足够的容量可以装该商品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$ ，m[n][j]=0；
- 若j≥ $w_n$ ，m[n][j]= $v_n$ 。

例子

在这里插入图片描述
根据递推关系式得到表中数据：

构造最优解(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)

核心算法

在这里插入图片描述

void Knapsack(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表示装入背包  
void Traceback(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>2ⁿ时，需要Ω(n*2ⁿ)计算时间。

所以，所以！！改进算法如下：

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

(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;
const int MAX = 1024;
int n; //物品个数
int c; //包的容量
int value[MAX]; //物品的价值
int weight[MAX]; //物品的重量
int x[MAX]; //n元0-1向量
int m[MAX][MAX]; //解的容器
void Input()
{
    cout<<"请先输入物品个数和包的容量(n c)：";
    cin>>n>>c;
    cout<<"请输入每件物品的重量和价值(v w)："<<endl;
    for(int i = 1; i <= n; ++i)
        cin>>value[i]>>weight[i];
}
//创建最优解
void Knapsack()
{
    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]);
            }
        }
    }
}
//获取最优解(即设法将求得的最优解输出出来)
void Traceback()
{
    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;
           cc -= weight[i];
        }
    }
    if(cc >= weight[1])
        x[1] = 1;
 
}
void Output()
{
    cout << "最优解为 : " << m[n][c] << endl;
    cout << "选择的物品的序号为 :" << endl;
    for(int i = 1; i <= n; ++i)
        if(x[i] == 1)
         cout << i << " ";
    cout << endl;
}
int main()
{
    Input();
    Knapsack();
    Traceback();
    Output();
}