【动态规划】（三）动态规划——完全背包

完全背包理论基础

  有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

回顾一下01背包的核心代码:

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

我们知道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数组来说，其实两个for循环嵌套顺序是无所谓的！ 但在应用中稍有变形则另说。

因为dp[j] 是根据 下标 j 之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

遍历物品在外层循环，遍历背包容量在内层循环，状态如图：

 

遍历背包容量在外层循环，遍历物品在内层循环，状态如图：

 
但在实际应用过程中：

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) 
{ 
// 遍历背包容量
    for(int j = weight[i]; j <= bagWeight ; j++) 
    { 
        递推公式
    }
}

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

// 先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) 
{
 // 遍历物品
    for(int i = 0; i < weight.size(); i++) 
    {
    递推公式
    }
}

零钱兑换Ⅱ

力扣链接

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例:
输入: amount = 5, coins = [1, 2, 5]
输出: 4

注意

• 0 <= amount (总金额) <= 5000
• 1 <= coin (硬币面额) <= 5000
• 硬币种类不超过 500 种
• 结果符合 32 位符号整数

本题为完全背包，装满背包的组合数

动态规划五部曲：

• dp[j]含义： 凑成总金额j的货币组合数为dp[j]
• 确定递推公式： dp[j] += dp[j - coins[i]];
• dp数组初始化： dp[0] = 1（递归的基础）, 其他为 0 （累加的初值）
• 确定遍历顺序： 组合 先物品后背包，顺序遍历
• 举例推导dp数组： 输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：

程序实现：

int change(int amount, vector<int>& coins) 
{
// dp[i] :  可凑成总金额为 i 的组合有 dp[i] 种 最终求dp[amount]
vector<int> dp(amount + 1, 0);
// 物品重量 coins[i]  物品价值 coins[i]
// 背包大小 amount
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];
}

组合总和Ⅳ

力扣原题

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:
nums = [1, 2, 3]
target = 4
所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7

完全背包，求不同的排列数。

因此本题只需在上题的基础上修改遍历顺序即可，对于求排列数，先遍历背包，后遍历物品。

举例来推导dp数组

程序实现：

int combinationSum4(vector<int>& nums, int target) 
{
// dp[i] :  组成目标数 i 的组合有 dp[i] 个
vector<int> dp(target + 1, 0);
// 物品重量 nums[i]  物品价值 nums[i] 
// 背包大小 target
dp[0] = 1;
// 遍历背包
for(int j = 0; j <= target; j++)
{
// 遍历物品
for(int  i = 0; i < nums.size(); i++)
{
if(j - nums[i] >= 0)
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}

爬楼梯（进阶版）

对基础题的爬楼梯进行修改： 改变每次可爬的最大步数

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

动态规划五部曲：

• dp[j]含义： 爬到有i个台阶的楼顶，有dp[i]种方法。
• 确定递推公式： dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]，那么递推公式为：

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

• dp数组初始化： dp[0] = 1，是递归的基础，其他为0，累加的初始化
• 确定遍历顺序： 这里属于背包的排序问题，因为1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！ 所以需要先遍历背包，后物品：

   // 遍历背包
  for (int i = 1; i <= n; i++) 
  {
  // 遍历物品
      for (int j = 1; j <= m; j++) 
      {
          if (i - j >= 0) 
          dp[i] += dp[i - j];
      }
  }
  

零钱兑换

力扣链接

  给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

完全背包，装满背包所花的物品最少个数

动态规划五部曲：

• dp[j]含义： 凑足总额为j所需钱币的最少个数为dp[j]

• 确定递推公式： 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]，所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的：

  dp[j] = min(dp[j], dp[j-coins[i]] + 1);
  

• dp数组初始化： dp[0] = 1, 其他为 INT_MAX，防止在取 min 时覆盖实际值

• 确定遍历顺序： 因为本题为求钱币的个数，无论是排列思想还是组合思想都不影响个数，因为遍历前后无关，无论哪个先遍历都可以的。

• 举例推导dp数组： 以输入：coins = [1, 2, 5], amount = 5为例：

程序实现：

int coinChange(vector<int>& coins, int amount) 
{
// dp[i] :  可凑成总金额为 i 的最少硬币数 最终求dp[amount]
vector<int> dp(amount + 1, INT_MAX);
// 物品重量 coins[i]  物品价值 coins[i]
// 背包大小 amount
dp[0] = 0;
// 遍历物品
for(int  i = 0; i < coins.size(); i++)
{
// 遍历背包
for(int j = coins[i]; j <= amount; j++)
{
if(dp[j - coins[i]] != INT_MAX)
dp[j] = min(dp[j - coins[i]]+1,dp[j]);
}
}
for(int num:dp)
cout << num << " ";
if(dp[amount] == INT_MAX)
return -1;
return dp[amount];
}

完全平方数

  给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n，返回和为 n 的完全平方数的 最少数量 。

示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9

同上题一样，求装满背包的物品个数，并且为组合问题

• 背包大小：n
• 物品价值 i * i

动态规划五部曲：

• dp[j]含义： 和为j的完全平方数的最少数量为dp[j]

• 确定递推公式： dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]，所以递推公式：

  dp[j] = min(dp[j - i * i] + 1, dp[j]);
  

• dp数组初始化： dp[0] = 0, 其他 INT_MAX

• 确定遍历顺序： 由于是求物品的个数，这与排列和组合都可以，因此先遍历物品后背包和先背包后物品都可以的。

• 举例推导dp数组：

 
程序实现：

// 任何一个正整数都可以 因为有 1
int numSquares(int n) 
{
// dp[i] :  组成和为 i 的完全平方数的最少个数 最终求dp[n]
vector<int> dp(n + 1, INT_MAX);
// 物品重量 i  物品价值  i * i
// 背包大小 n
//递推公式
//dp[j] = min(dp[j - i * i] + 1, dp[j])
dp[0] = 0;
// 遍历物品
for(int  i = 1; i * i <= n; i++)
{
// 遍历背包
for(int j = i * i; j <= n; j++)
{
if(dp[j - i * i] != INT_MAX)
dp[j] = min(dp[j - i * i]+1,dp[j]);
}
}
for(int num:dp)
cout << num << " ";
return dp[n];
}

单词拆分

力扣链接

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：
拆分时可以重复使用字典中的单词，并且字典中没有重复的单词。

示例 1：
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true

示例 2：
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

思路：
物品：wordDict  wordDict[i]
背包：s

递推公式：

if((j,i) && dp[j]) // j-i是在字典单词 且dp[j] = true
dp[i] = true;

 
动态规划五部曲：

• dp[j]含义： 字符串长度为 i 能组成则为 true 结果dp[s.size()]

• 确定递推公式：

  • 如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
  • 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true

• dp数组初始化： dp[0] = true，递归的根基，非0下标dp[i]为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词

• 确定遍历顺序： 这里是完全背包排列问题，因为 “leet” “code” 与"code" "leet"是两种不同的情况，因此需要先遍历背包，后遍历物品。

• 举例推导dp数组： 以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例，dp状态如图：

 
程序实现：

bool wordBreak(string s, vector<string>& wordDict) 
{
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
// dp[i] :  字符串长度为 i 能组成则为 true  结果dp[s.size()]
vector<bool> dp(s.size() + 1, false);
// 物品   wordDict  wordDict[i]
// 背包 s
// 物品能否把背包装满 物品可以重复使用  
// 递推公式
/*
if((j,i) && dp[j]) // j-i是在字典单词 且dp[j] = true
dp[i] = true;
*/
// 排列 先遍历背包
dp[0] = true;// 递推公式的基础
for(int i = 1; i <= s.size() ; i++)
{
// 遍历物品
for(int j = 0; j < i; j++)
{
// 起始位置   距离
string word = s.substr(j, i-j);
// i-j的单词在字典中
if(wordSet.find(word) != wordSet.end() && dp[j] == true)
dp[i] = true;
}
}
for(int i = 0; i < dp.size(); i++)
cout << dp[i] << " ";
return dp[s.size()];
}

背包问题总结

背包问题总结

原文地址：https://blog.csdn.net/weixin_46216674/article/details/142103484

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！