P1820 凑零钱 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2023年3月8日 11:17

代码随想录的写法（详解）

P1820

回复 0 | 赞 1 | 浏览 3.2k

每个物品可以使用多次，这是完全背包的模板题。把给的目标钱数当成背包容量，每个面值的货币当成物品，由于物品数量不限，这就转化成了完全背包的问题。根据carl哥的动归五部曲，首先定义dp数组下标含义，dp[i][j]表示，当背包容量为j时，用前i个物品将背包装满最少需要多少物品，在这题里就是钱数为j时，用前i个硬币凑到钱数j最少需要多少个硬币。第二步确定递推关系式，根据第i个物品能不能装入背包分成两种情况，若不能装入，即当前背包容量j>当前物品的重量item[i]，dp[i][j]就等于dp[i-1][j],若能装入，就可以选择装或者不装，取一个最小值，第三部确定初始条件，背包容量为0...

2022年4月30日 14:36

贪心

P1820

回复 1 | 赞 0 | 浏览 5.2k

#include <iostream> using namespace std; const int N = 11; int m, n, res, a[N]; int main() { cin >> m >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i]; for (int i = n; i > 0; i -- ) if (m % a[i] != m) res += m / a[i], m %= a[i]; if (m) puts("Imp...

2021年4月26日 15:48

动态规划：凑零钱问题

P1820

回复 0 | 赞 0 | 浏览 7.7k

#include <iostream> using namespace std; int main() { int M, K, value[1005], dp[1005] = {0}; while(cin >> M) { if(M == 0) break; cin >> K; for(int i = 0;i < K;i++) cin >> value[i]; for(int i = 1;i <= M;i++) { dp[i] = 999999; for(int ...

2021年1月31日 15:59

简洁

P1820

回复 0 | 赞 1 | 浏览 8.9k

#include<cstdio> #include <vector> #include <string> #include <string.h> #include<iostream> #include<algorithm> using namespace std; const int maxn=2000+5; const int INF=9999; int a[maxn]; int d[11]; int main() { int m,k; while(cin>>m) ...

题目凑零钱

题解数量4

热门题解

1 简洁

2 代码随想录的写法（详解）

3 贪心

4 动态规划：凑零钱问题