算法（十五） 背包dp

01背包问题

基础背包

int[] dp = new int[weight+1];
for(int i=1;i<=n;i++){
    for(int j=weight;j>=nums[i-1];j--){
        dp[j] = Math.max(dp[j-nums[i-1]]+nums[i-1],dp[j]);
    }
}
return dp[weight];

目标和

leetcode 494

思路：见代码注释

// 新思路，转化为01背包问题
	// 思考1:
	// 虽然题目说nums是非负数组，但即使nums中有负数比如[3,-4,2]
	// 因为能在每个数前面用+或者-号
	// 所以[3,-4,2]其实和[3,4,2]会达成一样的结果
	// 所以即使nums中有负数，也可以把负数直接变成正数，也不会影响结果
	// 思考2:
	// 如果nums都是非负数，并且所有数的累加和是sum
	// 那么如果target>sum，很明显没有任何方法可以达到target，可以直接返回0
	// 思考3:
	// nums内部的数组，不管怎么+和-，最终的结果都一定不会改变奇偶性
	// 所以，如果所有数的累加和是sum，并且与target的奇偶性不一样
	// 那么没有任何方法可以达到target，可以直接返回0
	// 思考4(最重要):
	// 比如说给定一个数组, nums = [1, 2, 3, 4, 5] 并且 target = 3
	// 其中一个方案是 : +1 -2 +3 -4 +5 = 3
	// 该方案中取了正的集合为A = {1，3，5}
	// 该方案中取了负的集合为B = {2，4}
	// 所以任何一种方案，都一定有 sum(A) - sum(B) = target
	// 现在我们来处理一下这个等式，把左右两边都加上sum(A) + sum(B)，那么就会变成如下：
	// sum(A) - sum(B) + sum(A) + sum(B) = target + sum(A) + sum(B)
	// 2 * sum(A) = target + 数组所有数的累加和
	// sum(A) = (target + 数组所有数的累加和) / 2
	// 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2
	// 那么就一定对应一种target的方式
	// 比如非负数组nums，target = 1, nums所有数累加和是11
	// 求有多少方法组成1，其实就是求，有多少种子集累加和达到6的方法，(1+11)/2=6
	// 因为，子集累加和6 - 另一半的子集累加和5 = 1(target)
	// 所以有多少个累加和为6的不同集合，就代表有多少个target==1的表达式数量
	// 至此已经转化为01背包问题了
	public static int findTargetSumWays4(int[] nums, int target) {
		int sum = 0;
		for (int n : nums) {
			sum += n;
		}
		if (sum < target || ((target & 1) ^ (sum & 1)) == 1) {
			return 0;
		}
		return subsets(nums, (target + sum) >> 1);
	}

	// 求非负数组nums有多少个子序列累加和是t
	// 01背包问题(子集累加和严格是t) + 空间压缩
	// dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
	public static int subsets(int[] nums, int t) {
		if (t < 0) {
			return 0;
		}
		int[] dp = new int[t + 1];
		dp[0] = 1;
		for (int num : nums) { // i省略了
			for (int j = t; j >= num; j--) {
				dp[j] += dp[j - num];
			}
		}
		return dp[t];
	}

最后一块石头的重量

leetcode 1049

思路：转化为找出一个数组中最接近和的一半的子序列和。答案就是sum - 2 * 子序列和，找最接近和的一半的子序列和就是01背包问题。背包容量为一半，然后找出价值最高的子序列和。

public int lastStoneWeightII(int[] stones) {
    int sum = 0;
    for (int stone : stones) {
        sum+=stone;
    }
    int near = findLSW(stones,sum/2);
    return sum - near - near;
}

private int findLSW(int[] stones, int i) {
    int[] dp = new int[i+1];
    for (int stone : stones) {
        for(int j=i;j>=stone;j--){
            dp[j] = Math.max(dp[j],dp[j-stone]+stone);
        }
    }
    return dp[i];
}

分组背包

模板题

同一个组的物品只能选一个，求最大价值。

思路：还是分为要跟不要。但是要的情况需要讨论要一组里的哪一个。所以dp[i][j] 中的i表示物品组，j表示背包容量。开始时可以按组号排序，一组一组处理即可。

// 严格位置依赖的动态规划
	public static int compute1() {
		int teams = 1;
		for (int i = 2; i <= n; i++) {
			if (arr[i - 1][2] != arr[i][2]) {
				teams++;
			}
		}
		// 组的编号1~teams
		// dp[i][j] : 1~i是组的范围，每个组的物品挑一件，容量不超过j的情况下，最大收益
		int[][] dp = new int[teams + 1][m + 1];
		// dp[0][....] = 0
		for (int start = 1, end = 2, i = 1; start <= n; i++) {
			while (end <= n && arr[end][2] == arr[start][2]) {
				end++;
			}
			// start ... end-1 -> i组
			for (int j = 0; j <= m; j++) {
				// arr[start...end-1]是当前组，组号一样
				// 其中的每一件商品枚举一遍
				dp[i][j] = dp[i - 1][j];
				for (int k = start; k < end; k++) {
					// k是组内的一个商品编号
					if (j - arr[k][0] >= 0) {
						dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - arr[k][0]] + arr[k][1]);
					}
				}
			}
			// start去往下一组的第一个物品
			// 继续处理剩下的组
			start = end++;
		}
		return dp[teams][m];
	}

	// 空间压缩
	public static int compute2() {
		// dp[0][...] = 0
		Arrays.fill(dp, 0, m + 1, 0);
		for (int start = 1, end = 2; start <= n;) {
			while (end <= n && arr[end][2] == arr[start][2]) {
				end++;
			}
			// start....end-1
			for (int j = m; j >= 0; j--) {
				for (int k = start; k < end; k++) {
					if (j - arr[k][0] >= 0) {
						dp[j] = Math.max(dp[j], arr[k][1] + dp[j - arr[k][0]]);
					}
				}
			}
			start = end++;
		}
		return dp[m];
	}

从栈中取出k个硬币的最大面值和

leetcode 2218

思路：以一个栈里面的硬币为分组。一组里面的元素就是拿一个硬币，两个硬币，三个硬币…得到的面值。一组我也只能拿一个。

   // piles是一组一组的硬币
// m是容量，表示一定要进行m次操作
// dp[i][j] : 1~i组上，一共拿走j个硬币的情况下，获得的最大价值
// 1) 不要i组的硬币 : dp[i-1][j]
// 2) i组里尝试每一种方案
// 比如，i组里拿走前k个硬币的方案 : dp[i-1][j-k] + 从顶部开始前k个硬币的价值和
// 枚举每一个k，选出最大值
public static int maxValueOfCoins1(List<List<Integer>> piles, int m) {
	int n = piles.size();
	int[][] dp = new int[n + 1][m + 1];
	for (int i = 1; i <= n; i++) {
		// i从1组开始（我们的设定），但是题目中的piles是从下标0开始的
		// 所以来到i的时候，piles.get(i-1)是当前组
		List<Integer> team = piles.get(i - 1);
		int t = Math.min(team.size(), m);
		// 预处理前缀和，为了加速计算
		int[] preSum = new int[t + 1];
		for (int j = 0, sum = 0; j < t; j++) {
			sum += team.get(j);
			preSum[j + 1] = sum;
		}
		// 更新动态规划表
		for (int j = 0; j <= m; j++) {
			// 当前组一个硬币也不拿的方案
			dp[i][j] = dp[i - 1][j];
			for (int k = 1; k <= Math.min(t, j); k++) {
				dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + preSum[k]);
			}
		}
	}
	return dp[n][m];
}

// 空间压缩
public static int maxValueOfCoins2(List<List<Integer>> piles, int m) {
	int[] dp = new int[m + 1];
	for (List<Integer> team : piles) {
		int t = Math.min(team.size(), m);
		int[] preSum = new int[t + 1];
		for (int j = 0, sum = 0; j < t; j++) {
			sum += team.get(j);
			preSum[j + 1] = sum;
		}
		for (int j = m; j > 0; j--) {
			for (int k = 1; k <= Math.min(t, j); k++) {
				dp[j] = Math.max(dp[j], dp[j - k] + preSum[k]);
			}
		}
	}
	return dp[m];
}

完全背包

模板题

一个物品可以重复取，求最大价值。

dp[i][j] = Max(dp[i-1][j],dp[i][j-w[i]]+v[i]) //拿了之后i也不减一，就可以拿多次。空间压缩需要正着遍历。

// 严格位置依赖的动态规划
	// 会空间不够，导致无法通过全部测试用例
	public static long compute1() {
		// dp[0][.....] = 0
		int[][] dp = new int[m + 1][t + 1];
		for (int i = 1; i <= m; i++) {
			for (int j = 0; j <= t; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j - cost[i] >= 0) {
					dp[i][j] = Math.max(dp[i][j], dp[i][j - cost[i]] + val[i]);
				}
			}
		}
		return dp[m][t];
	}

	// 空间压缩
	// 可以通过全部测试用例
	public static long compute2() {
		Arrays.fill(dp, 1, t + 1, 0);
		for (int i = 1; i <= m; i++) {
			for (int j = cost[i]; j <= t; j++) {
				dp[j] = Math.max(dp[j], dp[j - cost[i]] + val[i]);
			}
		}
		return dp[t];
	}