9.12零钱兑换(LC518-M)(开始完全背包,与01背包的不同仅在于遍历顺序)

2024-03-07 00:44

本文主要是介绍9.12零钱兑换(LC518-M)(开始完全背包,与01背包的不同仅在于遍历顺序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法:

这是一道典型的背包问题,一看到钱币数量不限,就知道这是一个完全背包。

但本题和纯完全背包不一样,纯完全背包是凑成背包最大价值是多少,而本题是要求凑成总金额的物品组合个数!

动规五步曲:

1.确定dp数组以及下标:

dp[j]:凑成总金额j的货币组合数为dp[j]

2.确定dp公式

dp[j] 就是所有的dp[j - coins[i]](考虑coins[i]的情况)相加。

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

求装满背包有几种方法,公式都是:dp[j] += dp[j - nums[i]];

3.dp数组初始化

组合-累加-dp[0]=1,一定不能为0

首先dp[0]一定要为1,dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话,后面所有推导出来的值都是0了。

下标非0的dp[j]初始化为0,这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]

4.确定遍历顺序

对于普通的完全背包问题:完全背包的两个for循环的先后顺序都是可以的。

但本题就不行了!

因为纯完全背包求得装满背包的最大价值是多少,和凑成总和的元素有没有顺序没关系,即:有顺序也行,没有顺序也行!

本题要求凑成总和的组合数,元素之间明确要求没有顺序。

本题是求凑出来的方案个数,且每个方案个数是为组合数。

那么本题,两个for循环的先后顺序可就有说法了。

我们先来看 外层for循环遍历物品(钱币),内层for遍历背包(金钱总额)的情况。

假设:coins[0] = 1,coins[1] = 5。

for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量dp[j] += dp[j - coins[i]];}
}

那么就是先把1加入计算,然后再把5加入计算,得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

所以这种遍历顺序中dp[j]里计算的是组合数!

如果把两个for交换顺序,代码如下:

for (int j = 0; j <= amount; j++) { // 遍历背包容量for (int i = 0; i < coins.size(); i++) { // 遍历物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}

背包容量的每一个值,都是经过 1 和 5 的计算,包含了{1, 5} 和 {5, 1}两种情况。

此时dp[j]里算出来的就是排列数!

5.举例推导dp数组

coins.size=3,amount=5

i=0:

j=coins[0]=1;j<=5;j++{

  • j=1:dp[1]=dp[1-1]+dp[1]=0+1=1
  • j=2:dp[2]=dp[1]+dp[2]=1+0=1
  • j=5 dp[5]=dp[4]+dp[5]=1+0=1}

i=1:

j=coins[1]=2;j<=5;j++{

j=2:dp[2]=dp[2]+dp[2-2]=1+1=2

j=3:dp[3]=dp[3]+dp[1]=1+1=2

。。。。}

正确代码:

class Solution {public int change(int amount, int[] coins) {int[] dp = new int [amount+1];dp[0] = 1;//其他dp值(除了0以外的),dp[i]=0for(int i=0; i<coins.length; i++){for(int j=coins[i]; j<=amount; j++){dp[j] += dp[j-coins[i]];}}return dp[amount];}
}

注意:

dp[0]=1,dp[i]=0(i !=0)

//初始化dp数组,表示金额为0时只有一种情况,也就是什么都不装dp[0] = 1;

时间空间复杂度:

  • 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度
  • 空间复杂度: O(m)

这篇关于9.12零钱兑换(LC518-M)(开始完全背包,与01背包的不同仅在于遍历顺序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/781901

相关文章

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

2. c#从不同cs的文件调用函数

1.文件目录如下: 2. Program.cs文件的主函数如下 using System;using System.Collections.Generic;using System.Linq;using System.Threading.Tasks;using System.Windows.Forms;namespace datasAnalysis{internal static

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

uva 10130 简单背包

题意: 背包和 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>