您现在的位置是:首页 >技术交流 >算法记录 | Day44 动态规划网站首页技术交流

算法记录 | Day44 动态规划

是菜鸡小小陈啊 2023-06-21 08:00:03
简介算法记录 | Day44 动态规划

完全背包

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

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

完全背包的物品是可以添加多次的,所以要从小到大去遍历

# 先遍历物品,再遍历背包
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])
        
# 先遍历背包,再遍历物品       
for j in range(bag_weight + 1):
    for i in range(len(weight)):
        if j >= weight[i]: dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

dp状态图如下:
动态规划-完全背包

518.零钱兑换 II

思路:

注意题目描述中是凑成总金额的硬币组合数。组合不强调元素之间的顺序,排列强调元素之间的顺序

1.确定dp数组以及下标的含义:dp[j]:凑成总金额j的货币组合数为dp[j]

2.确定递推公式:dp[j] = dp[j] + dp[j - coins[i]]

凑成总金额为 i 的方案数 = 「不使用当前 coin,只使用之前硬币凑成金额 j 的方案数」+「使用当前 coin凑成金额 j−coin的方案数」。

3.dp数组如何初始化:dp[0]=1,dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话,后面所有推导出来的值都是0了

4.确定遍历顺序:外层for循环遍历物品(钱币),内层for遍历背包(金钱总额),组合数

外层for遍历背包,内层for循环遍历物品,排列数

5.举例推导dp数组

输入: amount = 5, coins = [1, 2, 5] ,dp状态图如下:

518.零钱兑换II

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0 for _ in range(amount+1)]
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i],amount+1):
                dp[j] =  dp[j]  + dp[j - coins[i]]
        return dp[amount]

377.组合总和 Ⅳ

思路:

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

2.确定递推公式:dp[i] = dp[i]+dp[i - nums[j]]

dp[i] =「不使用当前 nums[j]方案数」+「使用当前 nums[j]凑成 i - nums[j]的方案数」

3.dp数组如何初始化:dp[0]=1

4.遍历顺序 :求排列数就是外层for遍历背包,内层for循环遍历物品

5.举例来推导dp数组

我们再来用示例中的例子推导一下:

377.组合总和Ⅳ

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0 for _ in range(target+1)]
        dp[0] = 1

        for i in range(1,target+1):
            for j in nums:
                if i >= j:
                    dp[i] +=  dp[i-j]
        return dp[target]
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。