01背包&完全背包学习记录

前言

背包问题是动态规划的一类，背包又分01背包 & 完全背包，各自有各自很鲜明的特点，虽同为背包，形式也很像，但是细节上很大不同。

一、01背包

01表示面对数组的每一个值（抽象），每个值只能取一次或者不取，此时的状态应该是二维的，不仅外层递推target，内层还需递推数组取当前值和不取当前值。

1、花样滑冰

一个运动员有energy的能量，可选择跳不同的动作actions[m][2]，actions[i][0]表示第i个动作要消耗的能量，actions[i][1]表示第i个动作得到的分，要求不能做同样的动作，问：运动员能得到的最大分数是多少？

2、二维递推

/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 

     * 运动员可得到的最高分
     *
     * @param energy  int整型 运动员体力值
     * @param actions int整型二维数组 二维数组i为动作号 actions[i][0]为动作i+1消耗体力,actions[i][1]为动作i+1得分
     * @return int整型
     */
    public int maxScore(int energy, int[][] actions) {
        int n = actions.length;
        int[][] f = new int[energy + 1][n + 1];// 体力为i前j的最大得分。

        for (int i = 1; i <= energy; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i][j - 1];
                if (actions[j - 1][0] <= i)
                    f[i][j] = Math.max(f[i][j], f[i - actions[j - 1][0]][j - 1] + actions[j - 1][1]);

            }
        }
        return f[energy][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二、完全背包

完全表示面对数组的每一个值（抽象），每个值可以取多次，所以不存在当前值是否取或不取，虽也需要for循环寻找最值，但意义完全不一样。

1、花样滑冰（可选择相同动作）

如果能选择同样的动作，则问题变为完全背包问题。

2、解

// 动作可重复，完全背包。
    public int maxScore2(int energy, int[][] actions) {
        int n = actions.length;
        int[] f = new int[energy + 1];// 体力为i的最大得分。

        for (int i = 1; i <= energy; i++) {
            for (int j = 1; j <= n; j++) {
                if (actions[j - 1][0] <= i)
                    f[i] = Math.max(f[i], f[i - actions[j - 1][0]] + actions[j - 1][1]);

            }
        }
        return f[energy];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、完全平方数

4、解

public int numSquares(int n) {
        int[] f = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                f[i] = Math.min(f[i], f[i - j * j] + 1);
            }
        }
        return f[n];
    }
1
2
3
4
5
6
7
8
9
10
11

总：这两完全背包有一些细微的区别，就是数组是否有序问题，可以剪枝。

总结

1）如果能对问题进行分类，才算看到了区别和细节，才算入了门。

2）01背包特指只能装一个/不装，就必须进行二维递推，不仅要递推target，还要递推取不取当前+前n-1的状态应该是前面的最值。

3）完全背包指一种东西可以装很多次，此时直接递推target即可，里面套for循环寻找最值。

4）两种背包虽然同套for循环，但一种是二维递推，一种是面向整个数组寻找最值。

参考文献

[1] LeetCode 完全平方数