假设有m种面值的货币,(为降低难度,m=5。money[5]={30,10,8,5,1})需要找给顾客n角现金,付款问题(payment problem)要求找到一个付款方案,本题要求:动态规划法求最优值,付出的货币张数最少是多少?
时间: 2024-02-13 08:07:10 浏览: 18
这道题可以使用动态规划算法解决,具体步骤如下:
1. 定义状态:设f(i)表示找i元钱最少需要多少张货币。
2. 初始化:f(0) = 0,因为找0元钱需要0张货币。
3. 状态转移方程:对于每个i元钱,我们需要枚举所有的面值j,找到一个最小的f(i - money[j]),然后加上1就是f(i)的值,即f(i) = min{f(i - money[j])} + 1。
4. 最终答案:f(n)就是找n元钱最少需要的货币张数。
下面是使用C++实现的代码:
```
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10010;
int f[N], money[5] = {30, 10, 8, 5, 1};
int main() {
int n;
cin >> n;
memset(f, INF, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 5; j++) {
if (i >= money[j]) {
f[i] = min(f[i], f[i - money[j]] + 1);
}
}
}
cout << f[n] << endl;
return 0;
}
```
输入n元钱后,程序会输出找n元钱最少需要的货币张数。