找零钱问题动态规划c语言
时间: 2023-09-07 18:15:06 浏览: 51
找零钱问题是一个典型的动态规划问题。假设我们有一定面额的硬币,如1元、5元、10元、20元、50元、100元,现在需要找零n元,问最少需要多少硬币才能找零成功。
我们可以使用动态规划来解决这个问题,具体的思路如下:
1. 定义状态:设f(i)表示找零i元所需的最少硬币数。
2. 状态转移方程:对于每个硬币面额j,如果i>=j,那么f(i)可以由f(i-j)转移而来,即f(i) = min{f(i-j)+1}。
3. 初始状态:f(0) = 0,其他f(i)的初始值可以设为一个很大的数,比如999999。
4. 最终结果:f(n)即为所求。
下面是使用C语言实现的代码:
```c
#include <stdio.h>
#include <limits.h>
#define MAX_COINS 6 // 硬币种类数量
#define MAX_VALUE 1000 // 找零的最大面额
int coins[MAX_COINS] = {1, 5, 10, 20, 50, 100}; // 硬币面额
int f[MAX_VALUE+1]; // f数组,f[i]表示找零i元所需的最少硬币数
int main()
{
int n; // 需要找零的金额
scanf("%d", &n);
f[0] = 0; // 初始状态
for(int i=1; i<=MAX_VALUE; i++)
f[i] = INT_MAX; // 初始值设为一个很大的数
for(int i=1; i<=n; i++)
{
for(int j=0; j<MAX_COINS; j++)
{
if(i >= coins[j] && f[i-coins[j]] != INT_MAX)
{
f[i] = f[i] < f[i-coins[j]]+1 ? f[i] : f[i-coins[j]]+1; // 状态转移方程
}
}
}
printf("%d\n", f[n]); // 输出结果
return 0;
}
```
运行结果:
```
输入:23
输出:3
```