前言

背包问题：
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。
问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

背包算法

用二维数组
dpi ，表示在面对前i个物品，且背包容量为j时所能获得的最大价值。

整个表格是从左到右，从上到下生成的。

重要推导过程：

我们来提取部分值的生成来一探究竟。

dp3

当 i = 3 即物品栏中有了c这个可选项；
当 j = 4 即背包容量为4 .

此时的总价值如何计算呢？

选择1 ： 不考虑新添加的物品。
此时 总价值 对应 i = 2 , j = 4 也就是 dp2 即等于8.

选择2： 考虑将新添加的物品放进去，此时由于新添加的物品会占用一定的空间。
总价值: dp3 +新物品的价值。即
dp3 + 6 = 9.

通过比较选择1和选择2即可得到最大价值为9.

dp3

选择1：
dp3 = dp2 = 8

选择2：
dp3 = dp3 + 6 = 11

所以 dp3 = 11.

dp3

选择1：
dp3 = dp2 = 8

选择2：
dp3 = dp3 + 6 = 14

所以 dp3 = 14.

代码实例

/**
 * 求最大背包装载价值
 * 每个物品只有一个，只能装一次。（01背包)
 *
 * 例如：
 *    重量  价值
 * a   1     3
 * b   2     5
 * c   3     6
 *
 * 背包最大重量  6
 *
 * 求 最大价值
 */
public class Solution {

    public int getMaxValue(int[][] items, int maxWeight){
        if (items == null || items.length == 0){
            return 0;
        }
        int itemNum = items.length;

        // 新建dp表
        int[][] dp = new int[itemNum][maxWeight + 1];

        for (int i = 0; i < maxWeight + 1; i++) {
            if (items[0][0] <= i){
                dp[0][i] = items[0][1];
            }
        }
        for (int i = 1; i < itemNum; i++) {
            for (int j = 0; j < maxWeight + 1; j++) {

                // 先复制为上一行的
                dp[i][j] = dp[i - 1][j];

                if (j >= items[i][0]){
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - items[i][0]] + items[i][1]);
                }

            }
        }

        return dp[itemNum - 1][maxWeight];

    }


    @Test
    void test(){
        System.out.println(getMaxValue(new int[][]{{1, 3}, {2, 5}, {3, 6}}, 6));
    }

}