• 代码随想录打卡第四十六天|完全背包 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ


    完全背包理论

    有N件物品和一个最多能背重量为W的背包。第i件物品的重量是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]);
    
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    遍历物品和背包的循环是否可以颠倒?
    在纯完全背包中,是可以的

    循环顺序与排列组合的关系

    外层for循环遍历物品,内层for遍历背包的情况 是组合数 不考虑元素顺序 因为后面的物品拿了就不能再取前面的了 所以无法生成排列数

    外层for循环遍历背包,内层for遍历物品的情况 是排列数 考虑元素顺序 这个时候 前后物品顺序被打乱可以被随便排列
    链接

    518.零钱兑换II

    **题目:**给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。
    题目链接: 518.零钱兑换II
    代码如下:

    class Solution {
        public int change(int amount, int[] coins) {
            //可以凑成的方式
            //先背包再物品
            //dp[i]表示凑成i的方式
            if(amount==0){
                return 1;
            }
            if(amount==1){
                return 1;
            }
            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];
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    377. 组合总和 Ⅳ

    题目: 给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
    题目数据保证答案符合 32 位整数范围。
    题目链接: 377. 组合总和 Ⅳ
    代码如下
    此题是排列 所以背包在外 物品在内

    class Solution {
        public int combinationSum4(int[] nums, int target) {
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int i = 0; i <= target; i++) {
                for (int j = 0; j < nums.length; j++) {
                    if (i >= nums[j]) {
                        dp[i] += dp[i - nums[j]];
                    }
                }
            }
            return dp[target];
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
  • 相关阅读:
    Java毕业设计项目源码Java基于springboot的高校专业实习管理系统的设计和开发
    34、camunda架构
    【校招VIP】数据库基础之数据类型
    expressDemo不能使用import
    鲜花商城系统设计与实现(Java+Web+MySQL)
    JavaScript-数组、函数
    MyBatis源码剖析之Mapper代理方式细节
    图神经推荐系统笔记整理
    面向对象编程三⼤特性 --封装、继承、多态
    Blend for Visual Studio 让XAML也可以像WinForm一样可视化设计,Blend 与Studio的区别
  • 原文地址:https://blog.csdn.net/weixin_44925329/article/details/133976209