0-1背包问题

      甲欲出去旅游，可携带20公斤的行李，已知甲想带的5件行李的重量及其在旅行中产生的效益如下表所示：

行李编号	I	II	III	IV	V
重量/千克	6	4	8	8	4
行李效益	8	4	8	10	2

为使所带的行李在旅行中产生最大的效益，请问甲应该带哪几件行李？

【分析】

       经典的0-1背包问题。

       我们先用回溯法解决该问题，穷举所有可能性，当然进行适当的“剪枝”提高效率。在所有的可能性中寻找最优方案，并记录最优方案和最优值。

 

       我们再考虑用动态规划解决问题：

设甲可携带的行李重量为c，每个行李的重量为w(i)（1 <= i <= n）（表示第i个行李的重量），而每个行李对应的效益为v(i) (1 <= i <= n)（表示第i个行李的效益），用x(i)来表示第i个行李是否应该携带，当x(i)为1时，表示携带，当x(i)为0时，表示不携带。

则该问题的目标函数为

       max z = ∑x(i)v(i) (1 <= i <= n) (i = 1, 2, 3, ……, n对应x和v的乘积的和)

约束条件为

       ∑w(i)x(i) <= c;

       x(i) ∈ {0, 1}, 1 <= i <= n;

 

       我们可以证明该问题具有最优子结构性质，即规模为n的问题的最优解必由它的子问题n – 1最优解得到。

       例如：我们已知前k – 1个行李的最优携带方式，现在我们要求有k个行李时的最优解（当然这k个行李包含前面所提到的k – 1个行李），此时k个行李时的最优解包含前 k – 1个行李的最优解。

       此时我们根据运用动态规划构建子问题间的递推关系：

设该问题的子问题

目标函数 max∑v(k)x(k) (k从i到n)

约束条件 ∑w(k)x(k) <= j (k从i到n)

               x(k) ∈ {0, 1}, i <= k <= n;

的最优值为m(i, j)，即可携带的行李重量为j，可选择的行李编号为i到n时的最优值。则有

当i = n时，m(i, j) = m(n, j);

(表示可携带的行李重量为j，可选择的行李编号只有n，即只有一个行李可供选择)

       当 j <= c 时， m(n, j) = 0;

       (表示可携带的行李重量不足以携带编号为n的行李，那么它的最优值为0)

       当 j > c 时， m(n, j) = v(j);

       (表示可携带的行李重量大于这个编号为n的行李重量，即我们可以携带该行李)

 

当 i != n时，

       当0 <= j <= w(i)时，m(i, j) = m(i + 1, j);

       (表示当前可携带的行李重量为j，判断编号为i的行李是否可选，当该行李的重量大于可携带的行李重量时，该行李不能被携带，即它的最优值应该为除去行李i后考虑可选择的行李编号从I + 1到n的最优值)

       当j > w(i)时，m(i, j) = max(m(i + 1, j), m(i + 1, j – w(i)) + v(i));

       (表示当前可携带的行李重量为j，判断编号为i的行李是否可选，当该行李的重量小于可携带的行李重量时，该行李可被携带也可以不被携带，那么此时应该分情况讨论，即我们要求当该行李不被携带时所具有的最优值和当该行李被携带后的最优值，这两者中最大的为该子问题的最优值。

根据递归关系写出程序。

【程序】

用java语言编写程序，代码如下：

运用回溯法解决问题：

public class Knapsack2 {
	public static void main(String[] args) {
		int n = 5;
		int c = 20;
		int[] w = {0, 6, 4, 8, 8, 4};
		int[] v = {0, 8, 4, 8, 10, 2};
		
		int[] max = new int[1];
		max[0] = 0;
		
		int[] tx = new int[n + 1];
		int[] x = new int[n + 1];
		solve(n, c, w, v, max, tx, x, 0, 1);
		
		for(int i = 1; i < n + 1; i++)
			System.out.print(x[i] + " ");
		
		System.out.println();
		System.out.println(max[0]);
	}
	//n表示物品数量，c表示当前剩余容量，w存储各个物品的重量，v存储各个物品的价值
	//max存储最大总价值，tx存储当前的方案，x存储最优方案，cv表示当前方案的总价值，index表示当前所指向的物品编号
	public static void solve(int n, int c, int[] w, int[] v, 
			int[] max, int[] tx, int[] x, int cv, int index) {
		if(index == n + 1) {
			if(c >= 0 && cv > max[0]) {
				max[0] = cv;
				
				for(int i = 0; i < n + 1; i++)
					x[i] = tx[i];
			}
			
			return;
		}
		
		//容量不足
		if(c < 0)
			return;
		
		//表示物品不携带
		tx[index] = 0;
		solve(n, c, w, v, max, tx, x, cv, index + 1);
		
		//表示物品携带
		tx[index] = 1;
		solve(n, c - w[index], w, v, max, tx, x, cv + v[index], index + 1);
	}
}

运用动态规划解决问题：

public class Knapsack1 {
	public static void main(String[] args) {
		int[] w = {0, 6, 4, 8, 8, 4};
		int[] v = {0, 8, 4, 8, 10, 2};
		int c = 20;
		
		int n = 6;
		int[] x = new int[n];
		int[][] m = new int[100][100];
		knapsack(n - 1, w, v, c, m);
		select(n - 1, c, w, x, m);
		
		for(int i = 1; i < n; i++)
			if(x[i] == 1)
				System.out.print(i + " ");
		System.out.println();			
	}
	//求各个子问题的最优解。用二维数组m[][]来存储m(i,j)的相应值
	public static void knapsack(int n, int[] w, int[] v, int c,
			int[][] m) {
		int jMax = Math.min(w[n] - 1, c);
		
		int j;
		for(j = 1; j <= jMax; j++)
			m[n][j] = 0;
		for(j = w[n]; j <= c; j++)
			m[n][j] = v[n];
		
		for(int i = n - 1; i > 1; i--) {
			jMax = Math.min(w[i] - 1, c);
			
			for(j = 1; j <= jMax; j++)
				m[i][j] = 0;
			for(j = w[i]; j <= c; j++)
				m[i][j] = Math.max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
		}
		
		m[1][c] = m[2][c];
		if(w[1] <= c)
			m[1][c] = Math.max(m[2][c], m[2][c - w[1]] + v[1]);
	}
	/*在剩余容量相同的情况下，从第i个物品到第n个物品中选择时，该问题的最优值如果等于从第i-1个物品到第n个物品的最优值，
	 * 说明对于从第i个物品到第n个物品中选择的问题的最优解第i个物品没有被选择
	 * 考虑只有第n个物品时，如果该问题的最优解为0，说明第n个物品没有被选择；如果该问题的最优解不为0，说明第n个物品被选择了。
	 */
	public static void select(int n, int c, int[] w, int[] x, int[][] m) {
		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];
			}
		
		if(m[n][c] == 0)
			x[n] = 0;
		else
			x[n] = 1;
	}
}

【结果】

回溯法：

输出最优方案，输出最优值

动态规划：

输出选取的行李编号