在计算机基础中，有个关于钱的经典问题：
给定一些面值的钱币，需要凑成一定金额的零钱，怎样凑才能使用到的钱币数最少?
#include <iostream>
#include <vector>
#define max_val 1e12;
using namespace std;
vector<double> money = {1,2,5,10,20,100};
double getMin(vector<double> money) {
double min = max_val;
for (auto& m: money){
min = min(min, m);
}
return min;
}
int get_min_m(double m) {
if (m < getMin(money)){
return 0;
}else (
for (auto& cash: money) {
if (cash == m)
return 1;
}
)
int res_m = infinit;
double c = 0;
for (auto& cash: money) {
int res_m = min(res_m, get_min_m(m - cash));
c = cash;
}
if (c != 0)
cout << c;
return res_m + 1;;
}
int dp(double m) {
double res_money = getMoneyRes(money);
vector<double> est_money(ceil(m));
int vel = 0;
for(double i =0; i < m; i+=res_money) {
if (i < getMin(money)) break;
else if (abs(i - getMin(money)) < 1e-9) {
vel = 1;
break;
}
int min_val = 1e10;
for(auto& m: money) {
min_val = min(min_val, est_money[i - m])
}
est_money[i] = min_val + 1;
}
return est_money[-1];
}
int main()
{
double cash_total = 10.0;
int res = get_min_m(m);
int res = dp(m)
cout << "Hello World";
return 0;
}
ref: https://zhuanlan.zhihu.com/p/138159413
https://zhuanlan.zhihu.com/p/138328448
