动态规划经典题目之二（找零钱）

布满荆棘的人生 2022-05-15 05:46 313阅读 0赞

### 1.问题描述 ###

现存在一堆面值为 1,2,5,11,20,50 面值的硬币，问最少需要多少个硬币才能找出总值为 N个单位的零钱？

### 2.问题分析 ###

定义Optimal\[i\]是找到总值为i的钱数所需要的最少硬币数量。那么，初始值应该为 Optimal\[0\] = 0; 0 元需要 0个硬币。

定义value\[\] = \{1,2,5,11,20,50\};

定义i = 1 至 N；

从 1元开始递推到N元，那么存在Optimal\[i\] = min\{Optimal\[i - value\[k\]\] + 1\} ，k = 1 ... value\_num ; 这个递推关系式，Optimal\[i\] 是凑成第i元的 最少硬币数，假设从前往后递推，那么此时，1元至i-1元 已经是最优解

当我确定Optimal\[i\]时， 我只要遍历一遍 value。每一次循环，就能知道使用value\[k\]，k=1...value\_size, 拼成i元，需要的最少零钱（即：min\_money = Optimal\[i - value\[k\]\] + 1）,所以拼成第i元的最优解，Optimal\[i\] = min\{Optimal\[i - value\[k\]\] + 1\} ，k = 1 ... value\_num ，

注：Optimal\[i\] 的初始值 = INF 即可。

### 3.DP代码 ###

#include <iostream>
    
    #define inf 0x3f3f3f3f;
    
    using namespace std;
    //value 存放零钱 value_num 多少种零钱 N 要找的钱的数量
    int dp_opt(int* value,int value_num,int N)
    {
    	int* opt = new int[N + 2];
    	opt[0] = 0;
    	for(int i = 1;i<=N;i++)
    	{
    		opt[i] = inf;
    	}
    	for(int i = 1;i<=N;i++)
    	{
    		int min_money = inf;
    		for(int j = 0;j<value_num;j++)
    		{
    			if(i >= value[j] && opt[i - value[j]] + 1 < min_money)
    			{
    				min_money = opt[i - value[j]] + 1;
    			}
    		}
    		opt[i] = min_money;
    	}
    	//for(int i = 0; i<=N;i++)
    	//	cout << opt[i] << " ";
    	//cout << endl;
    	return opt[N];	
    }
    
    int main()
    {
    	int value[5] = {1,2,3,5,11};
    	int N;
    	cin >> N;
    	cout << dp_opt(value,5,N) << endl;
    	return 0;
    }