动态规划算法——背包问题

问题描述

小偷去某商店盗窃，带有一个背包，容量是50kg,现在有以下物品（物品不能切分，且只有一个），请问小偷应该怎么拿才能得到最大的价值？

物品	重量	价值
物品1	10kg	60元
物品2	20kg	100元
物品3	40kg	120元

问题分析

我们把50kg的袋子，拆分成5份，里面的表格就表示 当前重量下能装的最多的钱，第一列表示要装的物品

	10kg	20kg	30kg	40kg	50kg
物品1	60	60	60	60	60
物品2	60	100	160	160	160
物品3	60	100	160	160	180

加入物品1：

1. 只有物品1时，无论袋子有多大容量，那么能得到的做多的钱就是为物品1的价值，即60元。

加入物品2：

1. 当袋子容量为10kg时，只能装下物品1，所以最多钱也就是60
2. 当袋子容量为20kg时，可以装下物品1或者物品2，但是物品1的钱要比物品2的钱少，所以装物品2更划算，所以最多钱也就是100
3. 当袋子容量为30kg时，可以同时装下物品1和物品2，此时最多钱也就是160
4. 当袋子容量为40kg时，同3
5. 当袋子容量为50kg时，同3

加入物品3：

1. 袋子容量为10kg时，装不下，所以最多钱还是60
2. 袋子容量为20kg时，装不下物品3，只能选择钱比较多的物品2，此时钱最多为100
3. 袋子容量为30kg时，装不下物品3，所以延续上次选择的160
4. 袋子容量为40kg时，此时可以选择装物品4或者装物品1+物品2；显然物品1+物品2所得到的钱(160)要比只装物品3(120)得到的钱多，所以选择装物品1+物品2，所以钱做多为160
5. 袋子容量为50kg时，可以装下物品1+物品2、物品1+物品3；显然物品1+物品3所得到的钱(180)要比物品1+物品2所得到的钱(160)多，所以选择装物品1+物品3，所以钱做多为180

由上述过程可以推出状态转移方程为：

Max(money[i] + res[i - 1][w-weight[i]],res[i - 1][w])

money[i]: 表示第i个物品的价值

w: 当前背包总容量

res[i - 1][w - weight[i]]：表示当前物品没有装入背包中时，背包中可以装下物品的最大价值

weight[i]: 第i个物品的重量

res[i - 1][w]: 当前物物品没有装时，背包中物品价值

代码实现

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        System.out.println("Hello, World!");
		dynamicAlgorithm();
    }
	
	public static void dynamicAlgorithm() {
		// 背包总重量
		int w = 50;
		// 物品个数
		int n = 3;
		// 每个物品的重量
		int[] weights = {10,20,40};
		// 每个物品的价值
		int[] money = {60,100,120};
		// 这个二维数组就是表示上面表格中的内容
		int[][] res = new int[n + 1][w + 1];
		// 每次加的物品
		for(int i = 1;i <= n; i++) {
			// 分割的背包
			for(int j = 1;j <= w; j++) {
				if(j >= weights[i - 1]) {
					int value = Math.max(money[i - 1] + res[i - 1][w - weights[i - 1]],res[i - 1][j]);
					res[i][j] = value;
				} else {
					res[i][j] = res[i - 1][j];
				}
			}
		}
		// 找路径
		int row = res.length - 1;
		int col = res[0].length - 1;
		while(row > 0 && col > 0) {
			// 从最后一个背包中开始找路径，如果最后一个背包中的物品价值和装了前一个物品的背包价值一样，说明最后一个物品
			// 装和不装一样，那么就应该从倒数第二个背包开始寻找(row--)，一次类推
			if(res[row][col] == res[row - 1][col]) {
				row -= 1 ;
			} else {
				// 如果当前背包中价值和前一个背包价值不一样，则说明当前背包中新装了物品，当然新装的物品就时当前的物品，
				// 所以用当前背包容量 - 前一个背包容量，就是当前物品的重量，那么剩余的背包容量，就是能装下的物品的最大价值
				// 所以下一次应该从第cole - weights[--row]个背包开始找
				System.out.println("选择重量为：" + weights[row - 1]+"的物品");
				// --row 是因为包含了背包边界（即数组边界）,
				col = col - weights[--row];
			}
		}
	}
}