动态规划-01背包问题

------使用 java 编写，逻辑上所有语言通用

一、什么是01背包

（1）概念

         01 背包问题是在 M 件物品取出若干件放在空间为 W 的背包里，每件物品的重量为 wight1 ， wight2 至 wightn ，与之相对应的价值为 money1 , money2 至 moneyn ；

         01 背包的约束条件是给定几种物品，每种物品都只有一个，对其判断在背包能承受的最大限度内能够放入价值多少的物品；

 

二、如何理解背包问题

（1）例题：

        现有一个 1 kg 价值为 15 元的苹果、一个 3 kg 价值为 20 元的哈密瓜 、一个 4kg 价值为 30 元的榴莲，用一个承重能力为 4 kg 的背包，问该背包能装入价值最大为多少元的水果？

（2）列表理解法

2.1

        根据例题，假设有下表的情况，即拥有 0 - 3 种水果、0 - 4 kg 重量的 5 个背包时，问在其中可放入水果的最大价值；

        ( 加入 不装入水果情况和 0 kg 的情况是为了将水果个数和背包重量刚好与坐标对其，可不加入 )

	0kg	1kg	2kg	3kg	4kg
不装入：0kg          0元
苹果：1kg        15元
哈密瓜：3kg        20元
榴莲：4kg        30元

 2.2

        不论是 0 kg 的背包还是不放入水果最终的价值都为 0 元，故将这两种情况直接填充为 0 元；

	0kg	1kg	2kg	3kg	4kg
不装入：0kg          0元	0元	0元	0元	0元	0元
苹果：1kg        15元	0元
哈密瓜：3kg        20元	0元
榴莲：4kg        30元	0元

2.3

        计算只有一个苹果的时候，1 - 4 kg 的背包中能放入价值为多少的水果；

        因为只有一个苹果，而 1 kg 的苹果在 1 - 4 kg 的情况都能放入，故只有一个苹果的情况下 1 - 4 kg 的背包都是 15 元；

	0kg	1kg	2kg	3kg	4kg
不装入：0kg          0元	0元	0元	0元	0元	0元
苹果：1kg        15元	0元	15元	15元	15元	15元
哈密瓜：3kg        20元	0元
榴莲：4kg        30元	0元

2.4

        计算当拥有苹果和哈密瓜两种水果的情况下，1 - 4 kg 的背包中能放入价值为多少的水果；

        因为哈密瓜为 3 kg 故 1 kg 和 2 kg 重量的背包中只能够放入苹果，故将前一行只有苹果的情况下所得到的价值传入；

        在满足哈密瓜放入的条件时，可放入的水果价值可能会出现两种情况：

        1.在没有哈密瓜的情况下已经是在当前重量下能放入水果的最大价值；

        2.放入一个哈密瓜，再计算出剩余的空间，再加上没有哈密瓜情况下剩余重量所能装入的最大价值；（因为已经放入了一个哈密瓜，没有第二个哈密瓜）

        找出 1 、2 当中更大的水果价值，就是当前背包能够装入水果的最大价值；

        故推出此公式：（ Max() 表示取较大值 ）

        Max( 当前重量的前一行所存储的水果价值，当前水果的价值 + 剩余空间在前一行的水果价值 )

	0kg	1kg	2kg	3kg	4kg
不装入：0kg          0元	0元	0元	0元	0元	0元
苹果：1kg        15元	0元	15元	15元	15元	15元
哈密瓜：3kg        20元	0元	15元	15元	20元	35元
榴莲：4kg        30元	0元

2.5

        使用推演出来的公式将有榴莲情况下的表格填充完整；

	0kg	1kg	2kg	3kg	4kg
不装入：0kg          0元	0元	0元	0元	0元	0元
苹果：1kg        15元	0元	15元	15元	15元	15元
哈密瓜：3kg        20元	0元	15元	15元	20元	35元
榴莲：4kg        30元	0元	15元	15元	20元	35元

（2）代码演示法

2.1

        根据上面的方法建立三个数组，一个存储水果重量，一个存储水果价值，一个每种情况下背包中水果的最大价值，别漏掉不装入水果时的情况；

        重量和价值根据表格直接填入即可，二位数组 bag 的行取水果个数，则直接取前面任意一个数组取长度即可，因为背包的重量为 4 kg ，故列数一共要取 0 - 4 共计 5 个位置；

 2.2

        因为重量小于等于背包存储量时公式为 Max( 当前重量的前一行所存储的水果价值，当前水果的价值 + 剩余空间在前一行的水果价值 ) ，故将当前所定义的几个数组转代入此公式得到 ：

                                      

        bag[i][j] = Math.max( bag[i-1][j] , money[i] + bag[i-1][j-wight[i]] );

        利用得出的公式遍历出整个数组；

 

 2.3 

        最后输出出数组的右下角元素就得到了问题的答案；

 

三、代码分享

public class DP_01Bag {
    public static void main(String[] args) {
        int[] wight = { 0 , 1 , 3 , 4 };
        int[] money = { 0 , 15 , 20 , 35 };
        int[][] bag = new int[wight.length][5];


        for (int i = 1; i < bag.length; i++) {
            for (int j = 1; j < bag[i].length; j++) {
                if ( wight[i] > j)
                    bag[i][j] = bag[i-1][j];
                else bag[i][j] = Math.max( bag[i-1][j] , money[i] + bag[i-1][j-wight[i]] );
            }
        }
        System.out.println( bag[bag.length-1][bag[0].length-1] );
    }
}