动态规划最优解 (0-1背包)

序言

场景: 一天深夜. 路过一家商品店, 门未锁, 附近无人. 于是溜入店中. 店内商品五花八门, 掂了掂自己的书包, 差不多能承重10公斤.

于是立刻挑了四件不超过10公斤的商品, 价值如下:

对于任意一件商品, 我只有拿和不拿两种选择, 不能对某件商品进行拆分.

该怎么拿使得价值最大而不会破包? …

广告: 用markdown写表格很麻烦, 但突然在网上发现一个神器: excel转markdown神器

思考

首先, 想到一种解决办法1!

把这四种物品的所有排列可能搞出来, 依次尝试, 这个复杂度2的n次方.

要是有几十个物品呢? 繁琐程度可想而知. 排除这种办法.

又想到一种貌似不错的解决办法2: 先算出四件商品单位重量下的价值(value/kg)

value/weight => value/kg 结果如下:

再由高到低排序得到: Item3>Item4>Item1>Item2

所以得到如下步骤:

1. 放商品3, 背包剩余重量=(10-2)=8kg, 检查还有无能放的?
2. 有- 放商品4, 背包剩余重量=(8-6)=2kg, 检查还有无能放的?
3. 没了…

所以最终得到的价值为商品3和商品4的价值总和(50+130)=180元

然而, 这并不是最优的解法. 随便把商品1和商品3放进去, 价值都是190.

所以很遗憾, 用这种简单的小计算可能会导致得到的价值反而最低.

动态规划

介绍

动态规划是解决最优问题的一种方法. 它可以解决很多动归问题.

我们刚才的问题0-1背包问题就是可以用它来解决的.

除此之外, 类似的还有”部分背包问题”, “完全背包问题”

如果用贪心算法来解决”0-1背包问题”, 得到的并不是最优解!

基本原理

再来看一下动规解决背包问题的原理:

假如在最优解场景下, 我们最终只能在n个物品中拿x个(Item1, Item2, Item3 … Itemx)

那么这x个物品在满足小于背包重量的同时就已经形成最优解.

假如拿走最后一个放入的物品Itemx. 该物品的价值为Vx, 重量为Wx.

拿掉后对于剩余x-1个物品, 在重量Wp-Wx, V-Vx下应该也成立最优解?

(Wp:背包的最大重量, V:最终总价值)

可以用反证法来推导.

上面的递推关系证明了在最优解下, 它的子解集也是最优解;

于是可以将全局最优解扩展为局部最优解, 通过一步步缩小递推;

初始最小解应该为背包承受重量(W)为0, 物品数量(N)为0;

下面将W和N作为两个标量, 定义为二维矩阵matrix[][];

因为有初始最小解(为0)的情况, 矩阵应该为matrix[N+1][W+1];

也就是N+1行, W+1列的二维数组;

将矩阵结合上述推导, 我们分出三种情况(item:物品个数, weight:背包承重数):

1. 初始解: item=0, weight=0

2. 选择的物品大于背包承重了, 很简单, 那就不放呗, 价值仍为matrix[i-1][w]!

3. 在不大于背包承重限制下, 对于是否要选择第x个物品, 我们判断的依据是什么?

   • a:如果不放, 价值为matrix[i-1][w];

   • b:如果放了, 价值为matrix[i-1][w] + matrix[i-1][w-wi]

   再来比较a,b值.若a>b则选a, a<b则选b

可以将上述推导具化为公式:

代码实现

分析推导完毕, 进入最激动人心的实现环节!

public class Knapsack {
	
	public static void main(String[] args){
		
		int packWt = 10;
		int[] itemWtArr = {7, 4, 2, 6};
		int[] itemValArr = {140, 60, 50, 130}; 
		System.out.println("动态最优解: " + knapsack(packWt, itemWtArr, itemValArr));
	}
	
	public static int knapsack(int packWt, int[] itemWtArr, int[] itemValArr){

		int itemCount = itemWtArr.length;
		int[][] matrix = new int[itemWtArr.length+1][packWt+1];
		
		//初始情况: 物品数为0
		for(int i=0; i<=packWt; ++i) {
			matrix[0][i] = 0;
		}
		
		//初始情况: 背包重数为0
		for(int i=0; i<=itemCount; ++i) {
			matrix[i][0] = 0;
		}
		
		for(int i=1; i<=itemCount; ++i){
			for(int j=1; j<=packWt; ++j){
				if(itemWtArr[i-1] <= j) { //物品重量 < 当前背包重量 
					/**
					 * 1.不加入该物品时该重量的最大价值: matrix[i-1][j]
					 * 2.当前物品的价值: itemValArr[i-1];
					 * 3.当前物品的重量 : itemWtArr[i-1];
					 * 4.背包剩余重量: j-itemWtArr[i-1];
					 * 5.可以容纳剩余重量的价值: matrix[i-1][j-itemWtArr[i-1]]
					 */
					int affordItemVal = matrix[i-1][j-itemWtArr[i-1]];
					//放还是不放? 得出子集最优解
					matrix[i][j] = Math.max(matrix[i-1][j], affordItemVal + itemValArr[i-1]);
				}else { //物品重量 >背包重量 => 不放
					int forwardItemVal = matrix[i-1][j];
					matrix[i][j] = forwardItemVal;
				}
			}
		}
		printMatrix(matrix);
		return matrix[itemCount][packWt];
	}
	
	public static void printMatrix(int[][] matrix){
		System.out.println("---------------------------------------");
		for(int i=0; i<matrix.length; ++i){
			for(int j=0; j<matrix[i].length; ++j){
				System.out.format("%4d", matrix[i][j]);
			}
			System.out.println("\n");
		}
		System.out.println("---------------------------------------");
	}
}

至此, 序言中提到的问题 通过推导和编码已经完全实现了!

图解

下面用表格来描述一下过程

在初始状态下(物品数量Item=0, 背包承受重量Weight=0):

得出最优矩阵:

取值验证

取值验证是个看似很傻, 但很有效的方法

我记得我在开始学习编程语言时, 第一次碰到双层for循环, 就是取值验证才理解

如果对前面的结果还有疑惑, 可以取值来验证之前的推导:

example 1: 分析item2,weight4 (V:60):

1. 能否放物品2 ? 可以啊! 物品2重量为4.
2. 不放物品2是否价值更大? 不是阿! 不放价值为0(看前一行数据)
3. 放入物品2后还能放? 不能啊! 放了之后背包剩余承重为0了

example 2: 再来分析一下item3,weight9 (V:190):

1. 不放物品3时的最大价值, 看前一行是140

2. 能放物品3么, 能啊!

3. 放上物品3之后还能再放么? 能啊! 放完之后还剩余(10-2)=8呢

4. 那计算当前物品的价值+可以容纳的剩余重量的价值:

   Vitem2+martix[item=2][weight=8]=50+140=190 190 > 140 啊. 肯定选钱多的.

the end