01背包问题

有 n 件物品和一个最多能背重量为 w 的背包。第i件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

每个物品只能用一次，那对于每个物品只有两种状态，取或者不取。暴力的解法可以使用回溯法搜索全部的情况，此时时间复杂度为$O(n^2)$，需要通过动态规划来优化。

定义dp数组

动态规划需要找到问题的最优子结构，在01背包问题中，貌似不存在一个所谓的最优子结构。但是，在思考物品装入背包这个过程时，我们是怎么判断能否放入的？是通过背包剩余的空间是否能容纳该物品来判断的，而上一个物品是否放进去，取决于上一次时剩余空间能否容纳上一个物品。所以，背包问题的最优子结构是下标为[0-i]的物品，放进容量为j的背包时，背包所容纳的最大价值，这也就是dp数组的定义。

确定递推公式

1. 不放物品i：相当于[0 - i-1]的物品任选，即dp[i-1][j]；
2. 放物品i：这时候需要背包剩余容量大于等于weight[i]，也就只能从dp[i-1][j-weight[i]]来，最大价值还得加上value[i]。

两种情况我们取较大值：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。

初始化dp数组

从递推公式可知，最终结果从第0行来，所以需要初始化dp[0][] 。

从dp数组定义：dp[0][]只能选0号物品，只要容量j能放进0号物品，最大价值就是value[0]，否则0。

for (int j = weight[0]; j <= bagSize; j++) {
	dp[0][j] = value[0];
}

确定遍历顺序

我们先看递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，dp[i][j]由dp[i-1][j]和dp[i-1][j-w]得来，所以需要从上到下遍历，从左到右其实无所谓（因为第0行已经初始化了，后面的行是基于上一行的，和同列的没关系）。那外层遍历物品还是外层遍历背包呢？在背包问题中，物品和背包的遍历顺序是很有讲究的。但是本问题求装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，所以先遍历那个都一样。这里采用外层物品内层背包的遍历顺序。

代码1（二维）

public int zeroOneWeightBag2D(int[] weight, int[] value, int bagSize){
    // 创建dp数组
    int[][] dp = new int[weight.length][bagSize + 1];

    // 初始化dp数组
    for (int j = weight[0]; j <= bagSize; j++) {
        dp[0][j] = value[0];
    }

    for (int i = 1; i < weight.length; i++) {
        for (int j = 1; j <= bagSize; j++) {
            if (j < weight[i]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
			}
		}
	}
    return dp[weight.length-1][bagSize];
}

一维dp

观察递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，dp[i][]从上一行dp[i-1][]得来。如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])。那更进一步，只使用一维数组来保存状态。

dp数组的定义就变为了dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。初始化dp数组，因为直接少了一维。在二维中，我们需要初始化的是第0行；在一维中，也是一样的。

遍历顺序是个变化很大的地方。在二维中，外层物品或者外层背包，物品从上到下，背包从左到右或从右到左；但在一维中，必须外层物品，物品从上到下，背包必须从右到左。因为在二维里，dp[i][j]依赖于dp[i-1][j-w]，一维中我们实际上是将下一行dp[i][j]覆盖在了上一行dp[i-1][j]上，如果背包还是从左到右，会覆盖掉dp[i-1][j]，这个会影响到dp[i][j+w]的计算。为了避免出现这个情况，只能从右到左遍历。

代码2（一维）

public int zeroOneWeightBag1D(int[] weight, int[] value, int bagWeight){
    // 定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
    int[] dp = new int[bagWeight + 1];
    // 遍历顺序：外层遍历物品，内层遍历背包容量
    // 针对初始化第0行，其实已经包括在这里面了
    for (int i = 0; i < weight.length; i++){
        for (int j = bagWeight; j >= weight[i]; j--){
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[bagWeight];
}

01背包变种

416. 分割等和子集

力扣链接

也就是，能否装满容量为总和一半的背包。

public boolean canPartition(int[] nums) {
    int n = nums.length;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += nums[i];
    }
    // 总和为奇数，不能平分
    if (sum % 2 != 0) {
        return false;
    }
    int size = sum / 2; // 背包大小为总和的一半
    int[] dp = new int[size + 1];
    for (int i = 0; i < n; i++) {
        for (int j = size; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
        // 剪枝一下，每一次完成内层的for-loop，立即检查是否dp[size] == size
        if (dp[size] == size)
            return true;
    }
    return dp[size] == size;
}

1049. 最后一块石头的重量 II

力扣链接

也是约等于平分成两半，装满容量为总和一半（target = sum / 2 向下取整）的背包，这就是一半（dp[target]），另一半（sum - dp[target]）减去这一半就是最后一块石头的重量。

public int lastStoneWeightII(int[] stones) {
    int sum = 0;
    for (int stone : stones) {
        sum += stone;
    }
    int size = sum / 2;
    int[] dp = new int[size + 1];
    for (int i = 0; i < stones.length; i++) {
        for (int j = size; j >= stones[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }
    return Math.abs(sum - 2 * dp[size]);
}

494.目标和

力扣链接

本题要如何使表达式结果为target，有 left - right = target；left + right = sum。则有 left = (target + sum)/2 。target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合，也就是装满容量为left的背包有几种方法。

这里dp定义、递推公式、初始化都有变化。dp[j] 表示：填满j（包括j）容积的背包，有dp[j]种方法。递推公式为dp[j] += dp[j - nums[i]]。初始化dp[0] = 1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递推结果将都是0。

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }

    //如果target的绝对值大于sum，那么是没有方案的
    if (Math.abs(target) > sum) return 0;
    //如果(target+sum)为奇数，也是没有方案的
    if ((target + sum) % 2 != 0) return 0;

    int size = (target + sum) / 2;
    int[] dp = new int[size + 1];
    dp[0] = 1;

    for (int i = 0; i < nums.length; i++) {
        for (int j = size; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[size];
}

474. 一和零

力扣链接

本题中strs 数组里的元素就是物品，每个物品都是一个！而m 和 n相当于是一个背包，两个维度的背包。

dp[i][j]：最多有i个0和j个1的最大子集的大小。递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)。

public int findMaxForm(String[] strs, int m, int n) {
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i < strs.length; i++) {
        int zeros = 0, ones = 0;
        for (char ch : strs[i].toCharArray()) {
            if (ch == '0') {
                zeros++;
            } else {
                ones++;
            }
        }
        for (int j = m; j >= zeros; j--) {
            for (int l = n; l >= ones; l--) {
                dp[j][l] = Math.max(dp[j][l], dp[j - zeros][l - ones] + 1);
            }
        }
    }
    return dp[m][n];
}