代码随想录算法训练营day46 | 完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ

完全背包

完全背包相对于01背包来说物品有无限个

代码的不同主要体现在遍历顺序上, 完全背包的背包重量不需要倒序遍历,因为物品有无限个,可以被无限添加;并且因为背包重量正序遍历,后续的值依赖于前面的值,因此背包和物品的内外层遍历也没有特定顺序

下面以物品外层循环,背包容量内层循环为例

def test_CompletePack(weight, value, bagWeight):
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # 遍历物品
        for j in range(weight[i], bagWeight + 1):  # 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    return dp[bagWeight]

if __name__ == "__main__":
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
    result = test_CompletePack(weight, value, bagWeight)
    print(result)

518. 零钱兑换 II

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

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

动态规划五部曲:

  1. 确认dp数组以及下标的含义:dp[j]表示凑成金额j有dp[j]种不同的方式
  2. 确认递推公式:dp[j] += dp[j-weight[i]]
  3. dp数组的初始化:dp[0] = 1
  4. 确认遍历顺序:物品在外,背包容量在内正序遍历
  5. 举例推导dp数组:
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount+1)
        dp[0] = 1
        for coin in coins:
            for j in range(coin, amount+1):
                dp[j] += dp[j - coin]
        return dp[amount]

377. 组合总和 Ⅳ

  1. 确定dp数组以及下标的含义:dp[j]代表总和为j的排列个数为dp[j]
  2. 确定递推公式:dp[j] += dp[j-nums[i]]
  3. 数组的初始化:dp[0] = 1
  4. 确定遍历顺序:因为是求排列,不同顺序算不同结果,因此背包重量在外层循环,物品在内层循环
  5. 举例推导dp数组:
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for j in range(target + 1):
            for num in nums:
                if j >= num:
                    dp[j] += dp[j-num]
        return dp[target]

最近更新

  1. MySQL运算符

    2024-06-09 07:44:04       0 阅读
  2. 数据分离(C++)

    2024-06-09 07:44:04       0 阅读
  3. Jira系统基本介绍

    2024-06-09 07:44:04       0 阅读
  4. 深入解析Spring Cloud:微服务架构的利器(下)

    2024-06-09 07:44:04       0 阅读
  5. Adam优化算法

    2024-06-09 07:44:04       0 阅读
  6. K-MEANS 算法的简单实现

    2024-06-09 07:44:04       0 阅读

热门阅读

  1. 使用 LLaMA-Factory 实现对大模型函数调用功能

    2024-06-09 07:44:04       4 阅读
  2. 二叉树----7-3 列出叶结点

    2024-06-09 07:44:04       4 阅读
  3. bat指令踩坑记录

    2024-06-09 07:44:04       3 阅读
  4. Web Dart前端:探索、挑战与未来展望

    2024-06-09 07:44:04       4 阅读
  5. 计算机视觉中的low-level与 high-level任务

    2024-06-09 07:44:04       5 阅读
  6. python记录之字符串

    2024-06-09 07:44:04       4 阅读
  7. Playwright 这个强大的自动化测试工具

    2024-06-09 07:44:04       4 阅读
  8. 安装 hbase(伪分布式)

    2024-06-09 07:44:04       4 阅读
  9. 密码学基本概念

    2024-06-09 07:44:04       4 阅读
  10. Python为项目中添加上彩色日志

    2024-06-09 07:44:04       5 阅读
  11. perl use HTTP::Server::Simple 轻量级 http server

    2024-06-09 07:44:04       3 阅读
  12. 面试 Redis 八股文十问十答第二期

    2024-06-09 07:44:04       2 阅读
  13. ASP.NET Core 中使用基本消息的 RabbitMQ 消费者

    2024-06-09 07:44:04       4 阅读