本文主要是介绍训练营第三十一天 | 494.目标和474.一和零动态规划:完全背包理论基础518.零钱兑换II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
494.目标和
力扣题目链接(opens new window)
难度:中等
给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例:
- 输入:nums: [1, 1, 1, 1, 1], S: 3
- 输出:5
解释:
- -1+1+1+1+1 = 3
- +1-1+1+1+1 = 3
- +1+1-1+1+1 = 3
- +1+1+1-1+1 = 3
- +1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
提示:
- 数组非空,且长度不会超过 20 。
- 初始的数组的和不会超过 1000 。
- 保证返回的最终结果能被 32 位整数存下。
思路:
本题要如何使表达式结果为target,
既然为target,那么就一定有 left组合 - right组合 = target。
left + right = sum,而sum是固定的。right = sum - left
公式来了, left - (sum - left) = target 推导出 left = (target + sum)/2 。
target是固定的,sum是固定的,left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。
(太巧妙了,知道是01背包问题,也在往这个方向想,可惜没想出来)
此时问题就转化为,装满容量为left的背包,有几种方法。
这里的left,就是背包容量。看到(target + sum) / 2 应该担心计算的过程中向下取整的影响。
例如sum 是5,S是2的话其实就是无解的,
(C++代码中,输入的S 就是题目描述的 target)
if ((S + sum) % 2 == 1) return 0; // 此时没有方案
同时如果 S的绝对值已经大于sum,那么也是没有方案的。
(C++代码中,输入的S 就是题目描述的 target)
if (abs(S) > sum) return 0; // 此时没有方案
这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
- 确定dp数组以及下标的含义
dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法。
- 确定递推公式
只要搞到nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。
例如:dp[j],j 为5,
- 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
- 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
- 已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包
- 已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包
- 已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢,也就是把 所有的 dp[j - nums[i]] 累加起来。
所以求组合类问题的公式,都是类似这种:
dp[j] += dp[j - nums[i]]
- dp数组如何初始化
如果数组[0] ,target = 0,那么 bagSize = (target + sum) / 2 = 0。 dp[0]也应该是1, 也就是说给数组里的元素 0 前面无论放加法还是减法,都是 1 种方法。
所以本题我们应该初始化 dp[0] 为 1。
dp[j]其他下标对应的数值也应该初始化为0,从递推公式也可以看出,dp[j]要保证是0的初始值,才能正确的由dp[j - nums[i]]推导出来。
- 确定遍历顺序
nums放在外循环,target在内循环,且内循环倒序。
- 举例推导dp数组
输入:nums: [1, 1, 1, 1, 1], S: 3
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4
dp数组状态变化如下:
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int k = nums.size();int sum = 0;for (int n = 0; n < k; n++) {sum += nums[n]; }if (abs(target) > sum) return 0;if ((sum + target) % 2) return 0;int left = (sum + target) / 2;vector<int> dp(left + 1, 0);dp[0] = 1;for (int i = 0; i < k; i++) {for (int j = left; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[left];}
};
474.一和零
力扣题目链接(opens new window)
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。
示例 1:
-
输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
-
输出:4
-
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。
示例 2:
- 输入:strs = ["10", "0", "1"], m = 1, n = 1
- 输出:2
- 解释:最大的子集是 {"0", "1"} ,所以答案是 2 。
提示:
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] 仅由 '0' 和 '1' 组成
- 1 <= m, n <= 100
思路:
本题中strs 数组里的元素就是物品,每个物品都是一个!
而m 和 n相当于是一个背包,两个维度的背包。
- 确定dp数组(dp table)以及下标的含义
dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
- 确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中,取dp[i][j]的最大值。
所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。
- dp数组如何初始化
因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。
- 确定遍历顺序
外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!
物品就是strs里的字符串,背包容量就是题目描述中的m和n。
代码如下:
for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}
}
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (string str : strs) {int zeroNum = 0, oneNum = 0;for (char c : str) {if (c == '1') oneNum++;else zeroNum++;}for (int i = m; i >= zeroNum; i--) {for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};
动态规划:完全背包理论基础
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。
背包最大重量为4。
物品为:
重量 | 价值 | |
---|---|---|
物品0 | 1 | 15 |
物品1 | 3 | 20 |
物品2 | 4 | 30 |
问背包能背的物品最大价值是多少?
01背包和完全背包唯一不同就是体现在遍历顺序上。
我们知道01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的,所以要从小到大去遍历,即:
// 先遍历物品,再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}
dp状态图如下:
在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序是无所谓的!
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
先遍历背包在遍历物品,代码如下:
// 先遍历背包,再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量for(int i = 0; i < weight.size(); i++) { // 遍历物品if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}cout << endl;
}
题目:
小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的重量,并且具有不同的价值。
小明的行李箱所能承担的总重量为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料可以选择无数次,并且可以重复选择。
void test_CompletePack() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagWeight = 4;vector<int> dp(bagWeight + 1, 0);for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;
}
int main() {test_CompletePack();
}
518.零钱兑换II
力扣题目链接(opens new window)
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
- 输入: amount = 5, coins = [1, 2, 5]
- 输出: 4
解释: 有四种方式可以凑成总金额:
- 5=5
- 5=2+2+1
- 5=2+1+1+1
- 5=1+1+1+1+1
示例 2:
- 输入: amount = 3, coins = [2]
- 输出: 0
- 解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
- 输入: amount = 10, coins = [10]
- 输出: 1
注意,你可以假设:
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
思路:
- 确定dp数组以及下标的含义
dp[j]:凑成总金额j的货币组合数为dp[j]
- 确定递推公式
dp[j] 就是所有的dp[j - coins[i]](考虑coins[i]的情况)相加。
所以递推公式:dp[j] += dp[j - coins[i]];
- dp数组如何初始化
首先dp[0]一定要为1,dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话,后面所有推导出来的值都是0了。
那么 dp[0] = 1 有没有含义,其实既可以说 凑成总金额0的货币组合数为1,
dp[0]=1还说明了一种情况:如果正好选了coins[i]后,也就是j-coins[i] == 0的情况表示这个硬币刚好能选,此时dp[0]为1表示只选coins[i]存在这样的一种选法。
- 确定遍历顺序
本题中我们是外层for循环遍历物品(钱币),内层for遍历背包(金钱总额),还是外层for遍历背包(金钱总额),内层for循环遍历物品(钱币)呢?
本题是求凑出来的方案个数,且每个方案个数是为组合数。
那么本题,两个for循环的先后顺序可就有说法了。
我们先来看 外层for循环遍历物品(钱币),内层for遍历背包(金钱总额)的情况。
代码如下:
for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量dp[j] += dp[j - coins[i]];}
}
假设coins[0] = 1,coins[1] = 5。
那么就是先把1加入计算,然后再把5加入计算,得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数!
如果把两个for交换顺序,代码如下:
for (int j = 0; j <= amount; j++) { // 遍历背包容量for (int i = 0; i < coins.size(); i++) { // 遍历物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}
背包容量的每一个值,都是经过 1 和 5 的计算,包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数!
- 举例推导dp数组
最后红色框dp[amount]为最终结果。
以上分析完毕,C++代码如下:
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包dp[j] += dp[j - coins[i]];}}return dp[amount];}
};
- 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度
- 空间复杂度: O(m)
在求装满背包有几种方案的时候,认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
这篇关于训练营第三十一天 | 494.目标和474.一和零动态规划:完全背包理论基础518.零钱兑换II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!