算法-完全背包硬币组合问题

ゞ浴缸里的玫瑰 2024-04-18 14:58 71阅读 0赞

## 1. 硬币组合问题 ##

给定硬币的面值数组，以及需要找零的目标值 target，输出能满足要求的最小硬币数量。

例如： coins = \[1, 2, 5\], amount = 12

可使用 2个 面值为5 的硬币和 1个面值为2的硬币满足要求，返回 3。

## 2. 解法 ##

完全背包问题，面值相同的硬币可以复用，使用动态规划法，外层遍历硬币，内层遍历目标金额

每趟使用一个硬币面值更新数组，数组最后一个元素值即为解
    dp[0]:0 dp[1]:1 dp[2]:2 dp[3]:3 dp[4]:4 dp[5]:5 dp[6]:6 dp[7]:7 dp[8]:8 dp[9]:9 
    dp[0]:0 dp[1]:1 dp[2]:1 dp[3]:2 dp[4]:2 dp[5]:3 dp[6]:3 dp[7]:4 dp[8]:4 dp[9]:5 
    dp[0]:0 dp[1]:1 dp[2]:1 dp[3]:2 dp[4]:2 dp[5]:1 dp[6]:2 dp[7]:2 dp[8]:3 dp[9]:3

public int coinChange(int[] coins, int target) {
        
        // coins = [1, 2, 5], target = 9
         if (amount == 0 || coins == null || coins.length == 0) {
        
                return 0;
            }
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            for (int coin : coins) {
        
                // 这是一个完全背包问题。完全背包需要将 0-1 背包中逆序遍历 dp 数组改为正序遍历
                for (int i = coin; i <= amount; i++) {
        
                    // 如果dp[j - coins[i]]未被更新过还是初始值，说明当前遍历过的硬币中还无法凑出这个面额，跳过
                    if (dp[i - coin] == Integer.MAX_VALUE) {
        
                        continue;
                    }
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
            return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，71人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划No.32 | 完全背包问题】完全背包模板题

【算法|动态规划No.32 | 完全背包问题】完全背包模板题

电玩女神/ 2024年04月27日 06:49/ 0 赞/ 74 阅读

相关算法-完全背包硬币组合问题

1. 硬币组合问题给定硬币的面值数组，以及需要找零的目标值 target，输出能满足要求的最小硬币数量。例如： coins = \[1, 2, 5\], amo...

ゞ浴缸里的玫瑰/ 2024年04月18日 14:58/ 0 赞/ 72 阅读

相关完全背包问题

[322. 零钱兑换][322.] 所谓的完全背包问题就是在01背包的基础上不再限制物品的使用数量,那么在一维的滚动数组的dp基础上,就是把第二层for循环的顺序由从后向前,

客官°小女子只卖身不卖艺/ 2024年04月01日 09:32/ 0 赞/ 78 阅读

相关完全背包问题

完全背包问题 1、参考资料 https://www.cnblogs.com/ClearMoonlight/p/10471401.html https://blog

淩亂°似流年/ 2022年11月27日 07:15/ 0 赞/ 146 阅读

相关背包问题-背包01-硬币找零

package 动态规划.背包01; import java.util.Arrays; import java.util.Scanner;

深藏阁楼爱情的钟/ 2022年07月12日 12:12/ 0 赞/ 187 阅读

相关完全背包问题

1. 问题描述有 N 种物品, 物品 i 的重量为 wi, 价格为 vi, 背包所能承受的最大重量为 W。其中, N,W,wi,vi≥0 若每种物品仅有一件,

短命女/ 2022年07月12日 06:37/ 0 赞/ 215 阅读

相关算法——背包问题 01背包+完全背包+多重背包

01背包：https://biancheng.love/problem/51/index 有n 种不同的物品，每个物品有两个属性，weight重量，value 价值，现在给一

ゞ浴缸里的玫瑰/ 2022年06月06日 10:41/ 0 赞/ 311 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 369 阅读

相关最少硬币问题（多重背包）

Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description 设

傷城~/ 2022年05月27日 06:15/ 0 赞/ 204 阅读

相关完全背包问题

完全背包问题跟01背包的区别是01背包每个物品只能选一次，总共就这几个。而完全背包问题是每个物品可以无限选，只要装得下。可以看成是有几种物品，每种都无限多个。可以

桃扇骨/ 2022年05月06日 15:27/ 0 赞/ 265 阅读