算法训练营Day38

发布时间:2024年01月12日

#Java #完全背包 #动态规划??? ????????????????????????

Feeling and experiences:

动态规划:完全背包理论基础

之前学习的是01背包,其特点在于:每个物品都只能取一个

而完全背包则是可以一个物品取多个。

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

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

零钱兑换II:力扣题目链接

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0

假设每一种面额的硬币有无限个。?

题目数据保证结果符合 32 位带符号整数。

示例 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[j] += dp[j-coins[i]];

? 外循环遍历每一种硬币。
? 内循环从该硬币面值开始,直到目标金额。
? 更新dp[j]的值:对于每个j,dp[j]增加dp[j?-?coins[i]]的值。这表示,如果你已经知道了组成金额j?-?coins[i]的方法数,那么只需加上当前硬币coins[i],就可以组成金额j。

(注意这里 内外 循环的区别
?

class Solution {
    public int change(int amount, int[] coins) {
    //因为硬币的数量可以随意取
    //这是一个完全背包问题

    //创建dp数组 ,dp数组的含义:装满容量为 j 的背包 有dp[j]种方法
    int []dp = new int[amount+1];

    //怎么递推出来的?
    //dp[j] += dp[j - coins[i]]; 


    //初始化dp数组:
    dp[0] = 1; //这里要初始化为1 ,不然后面递推不了了 

    for(int i =0;i< coins.length;i++){
        for(int j = coins[i];j<=amount;j++){
            dp[j] += dp[j-coins[i]];
        }
    }
    return dp[amount];
    }
}

乍一看,和01背包问题很像

以下是硬币只能取一次的代码:

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int i = 0; i < coins.length; i++) {
            for (int j = amount; j >= coins[i]; j--) {
                dp[j] += dp[j - coins[i]];
            }
        }

        return dp[amount];
    }
}

这里的关键变化是内循环的遍历方向。

由于每种硬币只能使用一次,所以我们必须从后向前更新?dp?数组。这样,当计算?dp[j]?时,dp[j?-?coins[i]]?还没有被当前的硬币影响,确保了每种硬币只被使用一次。

组合总和 Ⅳ:力扣题目链接

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1:

输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。

这道题就相当于是 零钱兑换II 求组合 变成了求排列

class Solution {
    public int combinationSum4(int[] nums, int target) {
    //关键:不同 序列被视作 不同组合

    //创建dp数组 含义: 得到target 有dp[target]种方法
    int []dp = new int[target+1];

    //递推公式:
    //dp[i] += dp[i-nums[j]];

    //初始化dp数组:
    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,3】 【3,1】 算两种不同的结果!

滟滟随波千万里,

何处春江无月明!

Fighting!
?

?

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