动态规划Day06(完全背包)

发布时间:2024年01月15日

完全背包

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

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

同样leetcode上没有纯完全背包问题,都是需要完全背包的各种应用,需要转化成完全背包问题,所以我这里还是以纯完全背包问题进行讲解理论和原理。

每件物品可以放入多次

为什么遍历物品在外层循环,遍历背包容量在内层循环?

01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了,一维dp数组的两个for循环先后循序一定是先遍历物品,再遍历背包容量。

在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序是无所谓的!

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

518.零钱兑换II(两次)

力扣题目链接(opens new window)

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

示例 1:

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

解释: 有四种方式可以凑成总金额:

  • 5=5
  • 5=2+2+1
  • 5=2+1+1+1
  • 5=1+1+1+1+1
看到题目的第一想法

? ? ? ?确定可以凑成dp的组合数

? ? ? ? 但是相同面额的可以重复,使用完全背包

看到代码随想录之后的想法

? ? ? ? 确定dp数组以及每个下标的含义

? ? ? ? dp[j] 为0~i之间能凑成j金额所需要的次数

? ? ? ? ?i为coins下标

????????确定递推公式

? ? ? ? 选中coins[i] ,则一共有j-coins[i]种能凑成j?

? ? ? ? 再加上本身的dp[j] ,就知道添加了coins[i]后一共要多少次

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

???????? 确定遍历顺序

? ? ? ? 可以重复添加物品,则从前往后

? ? ? ? dp数组初始化

? ? ? ? ?dp[0]=1为一切的源头,其他都为0

? ? ? ? 举例推导dp数组

? ? ? ??

自己实现过程中遇到的困难

? ? ? ? 我自己写成了? max(dp[j],dp[j-weight[i]]+1) 记混了

? ? ? ? 要理解组合数,求的是能凑成j的数目,需要累加j-coins[i]

class Solution {
    public int change(int amount, int[] coins) {
        //有多少种方式可以凑成对应面额
        // 确定dp数组以及每个下标的的含义
        // 能凑成目标金额的最大个数
        // 确定递推公式
        // dp[i]+=dp[i-nums[i]]
        // dp数组初始化
        // dp[0]=1;其他都为0
        // 确定遍历顺序
        // 从前往后,因为可以重复
        // 手动推导dp数组
        // 打印dp数组

        int dp[] = new int[amount+1];
        dp[0]=1;
        for(int i=0;i<coins.length;i++){
            //从前往后
            for(int j=coins[i];j<=amount;j++){
                dp[j]=dp[j]+dp[j-coins[i]];
            }
        }
        return dp[amount];

    }
}

377. 组合总和 Ⅳ

力扣题目链接(opens new window)

难度:中等

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

示例:

  • 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。

看到题目的第一想法

? ? ? ? 可以凑成目标正整数的组合的个数。

? ? ? ? 和零钱兑换II差不多

看到代码随想录之后的想法

? ? ? ? 确定dp数组以及每个下标的含义

? ? ? ? dp[j] 为0~i之间能凑成target所需要的次数

? ? ? ? ?i为nums下标

????????确定递推公式

? ? ? ? 选中nums[i] ,则一共有j-nums[i]种能凑成j?

? ? ? ? 再加上本身的dp[j] ,就知道添加了nums[i]后一共要多少次

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

???????? 确定遍历顺序

? ? ? ? 可以重复添加物品,则从前往后

? ? ? ? 比如说 (1231) 若可以凑成target

? ? ? ? 如果先物品后背包? 物品1 遍历完后? ,将再也不会遍历到1,之后遍历的是物品2,3,4

? ? ? ? 所以必须先背包后物品

? ? ? ? 外层循环是背包容量,物品按照 1 2 3 4的顺序,依次遍历 则 遍历完1,2,3还能遍历回1

? ? ? ? dp数组初始化

? ? ? ? ?dp[0]=1为一切的源头,其他都为0

? ? ? ? 举例推导dp数组

? ? ? ??

自己实现过程中遇到的困难

? ? ? ? 需要确认组合数和排列数的区别(看代码注释)

?????????组合数: 不强调顺序,不同顺序的都视为一个集合,必须先物品再背包
? ? ? ? ?排列数: 本题不同的地方在于不同顺序的视为不同集合,则必须先背包再物品
? ? ? ??

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 组合数:先遍历物品再遍历背包:每次选中一个物品都会遍历所有背包 1号物品一定在2号物品的前面
        // 排列数:先遍历背包再遍历物品:则每次选中一个背包都会遍历所有物品 每次都是 1号物品,2号物品。。。。 
        // 第二次 1号物品2号物品  1 2 交替 
        // 确定dp数组,以及对应下标的含义
        // 在0~i中满足总和为j的元素的个数,背包重量nums[i]  背包价值nums[i]
        // 确定递推公式
        // dp[j]+=dp[j-nums[i]]
        // dp数组的初始化
        // dp[0]=1 
        // 确定遍历顺序
        // 可以重复 从前往后
        // 组合数: 不强调顺序,不同顺序的都视为一个集合,必须先物品再背包
        // 排列数: 本题不同的地方在于不同顺序的视为不同集合,则必须先背包再物品
        // 手动推导dp数组
        int[] dp = new int[target+1];
        dp[0]=1;
        for(int j=0;j<=target;j++){
            for(int i=0;i<nums.length;i++){
                if(j>=nums[i]){
                    dp[j]+=dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
}

文章来源:https://blog.csdn.net/weixin_47455684/article/details/135609265
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。