背包问题

01背包问题

题意概要：有 𝑛个物品和一个容量为 𝑊的背包，每个物品有重量 𝑤𝑖和价值 𝑣𝑖 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

每个物品只能选一次, 属于01背包问题, 要总价值最大属于最值问题.

定义dp[i][j]是选取前i个物品后, 重量不超过j的最大价值.状态转移方程是:dp[i][j] = max(dp[i - 1][j] , dp[i-1][j-w[i]] + v[i] ) 这里的j要大于w[i].

状态转移方程的推导:要求选取前i个物品后, 重量不超过j的最大价值, 可以利用最优子问题选取前i-1个物品,重量不超过j, 或者重量不超过j-w[i] 的最大价值. 分别对应选取i与不选去i的情况. 将问题分解成了两个最优子问题.

也可以采取另一种推导方式(来自oiwiki): 假设当前已经处理好了前 𝑖 −1 个物品的所有状态，那么对于第 𝑖 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 𝑓𝑖−1,𝑗；当其放入背包时，背包的剩余容量会减小 𝑤𝑖，背包中物品的总价值会增大 𝑣𝑖，故这种情况的最大价值为 𝑓𝑖−1,𝑗−𝑤𝑖 +𝑣𝑖。

可以利用滚动数组优化: 应为计算dp[i][j]时只会用到上一次的dp[i-1], 因此可以用一个数组dp[j]来保存选择上一个元素的重量不超过j的最大价值. 这个时候计算dp[j]需要从尾到头遍历, 计算j较大的,会用到j较小的, 如果j较小的先更新, 就dp[j]就不是上一次选择的最大价值了.

核心代码:

//这里数组下标假设从1开始.
for(int i = 1; i < n + 1; i++) {
	for (int j = W; j >= w[i]; j--) {
		dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
	}
}

494. 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

要看出这道题是01背包问题不那么明显: 可以先将所有+元素和看P, -元素和为N. 要求P - N = target;

另外知道P + N = sum(所有数字和). sum和target都已知, 可求的P= (target+sum) / 2.

这样就将这个问题转换成了选择元素使其总和为P. 并寻找其所有组合个数.

选择元素, 达到总和P. 01背包问题.

应为是寻找所有组合个数, 定义dp[i][j] 为选取前i个元素时,达到总和为j的组合个数.

转移:假设找到了所有dp[i][j]; 要计算dp[i+1][j] , 有两种情况:选取i+1,有 dp[i][j-num[i+1]]种组合

不选i+1,dp[i][j]种组合. 二者相加, 即可得dp[i+1][j].

因为依然是指利用选择上一次元素的dp值来计算, 所以可以用滚动数组优化.

核心代码:

//这里数组下标假设从1开始.
for(int i = 1; i < n + 1; i++) {
	for (int j = P; j >= num[i]; j--) {
	//这里跳过j<num[i]的情况, 应为这种情况不可能选i.所以dp[j]不变.
		dp[j] = dp[j] + dp[j - num[i]];
	}
}

416. 分割等和子集

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。该题可以转换成选择元素, 使其总和为sum/2. sum已知, 所以是01背包问题,存在性判断.

定义问题:选取前i个元素后, 是否可以达成总和为j. bool值.

转移: dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]

滚动数组优化: j从target开始, 向后遍历 dp[j] = dp[j] || dp[j-nums[i]]

初始化: dp[0] = true.

核心代码

for (int num : nums) {
    for (int j = target; j >= num; j--) {
        dp[j] = dp[j] || dp[j - num];
    }
}

完全背包问题

01背包元素只有选与不选两种可能, 如果元素可以选多次, 则是完全背包问题.

Q26. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

典型的完全背包问题, 求最值.

与背包问题稍有不同的是,这里的W是要恰好装满的.

定义dp[j] = 凑成金额为j的最少的硬币数. 转移: 要计算dp[j], 需要用到dp[j-coin[i]],且j>coin[i].

dp[j] = min(dp[j-coin[i]],…) .

核心代码

for(int j = 1; j <= amount; j++) {
	for (int i = 0; i < coins.size(); i++) {
		if (j >= coin[i])
			dp[j] = min(dp[j],dp[j-coins[i]+1)
		}
}

应为min函数不在意元素顺序, 所以这里硬币的添加顺序并不影响.所以可以按任意顺序添加.但是组合问题并不适用.

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数

同样是完全背包问题,只不过是求组合总数.

这里dp[j]表示金额为j的组合总数, 转移: 要计算dp[j], 需要用到dp[j-coin[i]],且j>coin[i].

dp[j] = dp[j-coin[i]],…之和.

但是,这个解法是错的. 这个解法计算的是排列而不是组合.

为什么? 这个解法可以看成是计算j-coin的组合数, 将其相加,得到j的组合数.但是由于没有限制硬币添加的顺序, 会出现{2,1}. {1,2}被看成两种组合的情况.

解决办法:限制硬币加入的顺序. dp[j]含义变成在添加前i个硬币后, 达成金额为j的组合个数.

转移方程: dp[j] = dp[j] + dp[j-coin[i]]

核心代码:

for(int i = 1; i < coins.size(); i++) {
	for (int j = coin[i]; j < amount; j++) {
		dp[j] = dp[j] + dp[j - coin[i]];
}

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

和零钱兑换I 类似. 零钱的数额是完全平方数,而且是小于n的, amount = n;

零钱组合是1到小于等于sqrt(n)的整数的完全平方.

这里定义问题:dp[i][j]代表选择前i个元素时, 总和为j的最少数量.

转移: dp[i][j] = min( dp[i-1][j], dp[i-1][j-nums[i]]+1, dp[i-1][j- nums[i]*2] -2 ,…);

这样的转移方程很低效并且重复计算, 实际上后一项等于 dp[i][j-nums[i]].

因此dp[i][j] = min(dp[i-1][j], dp[i][j-nums[i]]+1). 后一项的意义是至少用了一次nums[i]. 前一项的意义时不用nums[i]. 有这两项中的最小值成为dp[i][j].

再用一维数组优化时, 就需要j从前往后遍历, 因为越小的值需要更新过后的(也就是用了nums[i]的).

for (int num : nums){
            for (int j = num; j < n+1; j++) {
                dp[j] = Math.min(dp[j], dp[j - num]+1);
            }
        }

377. 组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。这里组合考虑顺序, 即排列.

完全背包问题, 寻找排列. 应为时寻找排列, 元素的顺序不定, 可以用上面提到的计算总和为j的排列数 = dp[j]

dp[j] = dp[j-coin[i]] +…

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

总结

背包问题我将它看成从数组中选择(选择多次,或只能选一次)数字, 使其总和达到target. 在此基础上求最小/大选择个数, 或则组合总数.

解决这类问题的范式时利用动态规划, 状态转移则是每次选择数字时发生的.