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

问题描述

 给定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(); }

测试样例

输入 请先输入物品个数和包的容量(n c)：4 8 请输入每件物品的重量和价值(v w)： 2 1 1 4 4 2 3 3

输出 最优解为 : 9 选择的物品的序号为 : 1 3 4