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

[TOC]

序言

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

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

Item1Item2Item3Item4
Weight7426
Value1406050130

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

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

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

思考

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

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

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

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

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

Item1Item2Item3Item4
value/kg20152521.5

再由高到低排序得到: 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

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

代码实现

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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):

ValueWeight0Weight1Weight2Weight3Weight4Weight5Weight6Weight7Weight8Weight9Weight10
Item000000000000
Item10
Item20
Item30
Item40

得出最优矩阵:

ValueWeight0Weight1Weight2Weight3Weight4Weight5Weight6Weight7Weight8Weight9Weight10
Item000000000000
Item10000000140140140140
Item20000606060140140140140
Item30050506060110140140190190
Item40050506060130140180190190

取值验证

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

我记得我在开始学习编程语言时, 第一次碰到双层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

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×