侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第四十四天 | 完全背包;零钱兑换;组合总和

thinkTV
2023-06-01 / 0 评论 / 0 点赞 / 119 阅读 / 1,176 字 / 正在检测是否收录...

1. 完全背包理论基础

代码随想录:原文

1.1 完全背包

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

完全背包和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数组来说,其实两个for循环嵌套顺序是无所谓的

1.2 测试代码

// 先遍历物品,在遍历背包
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();
}

2. 零钱兑换

代码随想录 : 原文

力扣题目:518.零钱兑换II

2.1 思路

纯完全背包是凑成背包最大价值是多少,而本题是要求凑成总金额的物品组合个数

组合不强调元素之间的顺序,排列强调元素之间的顺序

动规五步曲

  1. 确定dp数组以及下标的含义
  • dp[j]:凑成总金额j的货币组合数为dp[j]
  1. 确定递推公式
  • 递推公式:dp[j] += dp[j - coins[i]];
  1. dp数组初始化
  • dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话,后面所有推导出来的值都是0了。
  • 下标非0的dp[j]初始化为0,这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
  1. 确定遍历顺序
  • 本题要求凑成总和的组合数,元素之间明确要求没有顺序
  • 外层for循环遍历物品(钱币),内层for遍历背包(金钱总额),这种遍历顺序中dp[j]里计算的是组合数
  • 外层for循环遍历背包(金钱总额),内层for遍历物品(钱币),这种遍历顺序中dp[j]里计算的是排列数
  1. 举例推导dp数组

图片-1

2.2 代码实现

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)

3. 组合总和

代码随想录 : 原文

力扣题目:377. 组合总和 Ⅳ

3.1 思路

本题题目描述说是求组合,但又说是可以元素相同顺序不同的组合算两个组合,其实就是求排列

动规五部曲

  1. 确定dp数组以及下标的含义
  • dp[i]: 凑成目标正整数为i的排列个数为dp[i]
  1. 确定递推公式

求装满背包有几种方法,递推公式一般都是dp[i] += dp[i - nums[j]];

  1. dp数组初始化

dp[0] = 1 , 非0下标的dp[i]初始为0

  1. 确定遍历顺序
  • 如果求组合数就是外层for循环遍历物品,内层for遍历背包。
  • 如果求排列数就是外层for遍历背包,内层for循环遍历物品。
  • 本题遍历顺序最终遍历顺序:target(背包)放在外循环,将nums(物品)放在内循环,内循环从前到后遍历。
  1. 打印dp数组

图片5

代码实现

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 0; i <= target; i++) { // 遍历背包
            for (int j = 0; j < nums.size(); j++) { // 遍历物品
                if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};
  • 时间复杂度: O(target * n),其中 n 为 nums 的长度
  • 空间复杂度: O(target)
0

评论区