代码随想录刷题60Day
目录
前言
目标和（01背包）
一和零（01背包）
零钱兑换（多重背包）
排列总和（多重背包）
前言
这两天都是背包问题，其中的01背包的一些应用问题需要一定的数学建模能力，需要i将实际问题简化成我们熟悉的背包问题；而这两天的多重背包问题还算比较基础，但也要我明白了动态规划中dp数组遍历顺序的重要性与决定性。
目标和（01背包）
int findTargetSumWays(vector<int>& nums, int& S)
{
int sum = 0;
const int size = nums.size();
for (int i = 0; i < size; ++i)
sum += nums[i];
if (sum < abs(S))
return 0;
if (S < 0)
S *= -1;
if ((S + sum) & 1)return 0;
int target = (S + sum) / 2;
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); ++i)
{
for (int j = target; j >= nums[i]; --j)
{
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}一和零（01背包）
int findMaxForm(vector<string>& strs, int m, int n)
{
vector<vector<int>> nums;
for (int i = 0; i < strs.size(); ++i)
{
if (strs[i].size() > (m + n))continue;
int zero = 0;
int one = 0;
for (int j = 0; j < strs[i].size(); ++j)
if (strs[i][j] == '0')
++zero;
else
++one;
if (zero <= m && one <= n)
nums.push_back({ zero, one });
}
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i < nums.size(); ++i)
{
int cZero = nums[i][0], cOne = nums[i][1];
for (int j = n; j >= cOne; --j)
for (int k = m; k >= cZero; --k)
dp[j][k] = max(dp[j][k], dp[j - cOne][k - cZero] + 1);
}
return dp[n][m];
}零钱兑换（多重背包）
文章来源：https://www.toymoban.com/news/detail-670594.html
int change(int amount, vector<int>& coins)
{
const int size = coins.size();
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i < size; ++i)
for (int j = coins[i]; j <= amount; ++j)
dp[j] += dp[j - coins[i]];
return dp[amount];
}排列总和（多重背包）
文章来源地址https://www.toymoban.com/news/detail-670594.html
int combinationSum4(vector<int>& nums, int target)
{
const int size = nums.size();
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; ++i)
for (int j = 0; j < size; ++j)
{
if (nums[j] <= i && (dp[i] < INT_MAX - dp[i - nums[j]]))
dp[i] += dp[i - nums[j]];
}
return dp[target];
}到了这里，关于【算法日志】动态规划刷题：01背包问题，多重背包问题(day37,day38)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
