背包问题

01背包

Leetcode474(一和零)😍哪里有零

上图为题目简介，这个题目还是非常的硬核的，01背包的集大成者，相信做完这个题目，你一定知道01背包究竟改怎么解决了。

public int findMaxForm(String[] strs, int m, int n) {
    int length = strs.length;
    int[][][] dp = new int[length + 1][m + 1][n + 1];
    // 返回最大子集的长度 dp[i][j][p] 表示 取前i个元素，0容量为j,1容量为p的子集最大长度
    dp[0][0][0] = 0;
    // 初始化数组
    // dp[i+1][j][p] = dp[i][j-nums[j]][p-nums[p]]
    int[][] arr = new int[length +1][2];
    for (int i = 0; i < length; i++) {
        String str = strs[i];
        for (int j = 0; j < str.length(); j++) {
            if (str.charAt(j) == '0') {
                arr[i+1][0]++;
            }else {
                arr[i+1][1]++;
            }
        }
    } // 计算出每个字符的0个数和1个数
    // 注意偏移量
    for (int i = 1; i <= length; i++) {
        // 为什么初始值 i = 1 ? 因为 i = 0 是没有意义的
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                if (j >= arr[i][0] && k >= arr[i][1]) {
                    dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-arr[i][0]][k-arr[i][1]] + 1);
                }else {
                    dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
    } // 最后使用三维循环解决
    // 注意长度为最外面的循环
    return dp[length][m][n];
}

此题需用三维数组来解决，如果想优化空间复杂度，也可以使用滚动数组。重点：滚动数组记得使用倒序遍历，这样可以保证每个元素只被使用一次。

完全背包

理论

• 完全背包的滚动数组需要正序遍历
• 求组合数就是外层循环遍历物品，内层循环遍历背包
• 求排列数就是外层循环遍历背包，内层循环遍历物品