贪心算法——找纸币问题
最后更新于:2022-04-01 20:19:49
问题主题:找钱 |
问题描述: 假设有1元、2元、5元、10元、20元、50元、100的纸币分别为c0, c1, c2, c3, c4, c5, c6,张。现在要用这些钱来支付K元,至少要用多少张纸币?如果能找,则输出纸币的张数,不能找则输出No 限制条件: 0<=c0, c1,c2,c3,c4,c5,c6<=109 0<=K<=109 |
样例: 输入 C0=3, c1=0, c2=2, c3=1, c4=0, c5=3, c6=5 输出 6 |
#include "iostream"
using namespace std;
const int N = 7; static int K = 6200; int min(int num1, int num2);
int momeyCount[N] = {3, 0, 2, 1, 0, 3, 5}; int value[N] = {1, 2, 5, 10, 20, 50, 100};
int giveChange() { int num = 0; for(int i = N-1; i >= 0; i --) { int c = min(K/value[i], momeyCount[i]); K = K - c * value[i]; num += c; } if(K > 0) num = -1; return num; }
int min(int num1, int num2) { return num1 < num2 ? num1 : num2; }
int main() { int result = giveChange(); if(result != -1) cout << result << endl; else cout << "NO" << endl; return 0; }
|