贪婪算法——换零钱

不念不忘少年蓝@ 2022-09-06 10:29 203阅读 0赞

## 算法思路 ##

*  从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。
 *  当达到算法中某一步不能不能再继续前进时，就停止算法，给出近似值。

--------------------

## 存在的问题 ##

*  不能保证最后的解是最优的。
 *  不能通过求最大或最小解问题。
 *  只能求满足某些约束条件的可行解的范围。

--------------------

## 实现过程 ##

*  从问题的某一初始解出发：
 *      while   是否达到（或近似达到）设定总目标
 *      求出可行解的一个解元素；
 *      由所有解元素组合成问题的一个可行解；

--------------------

## 实例 ##

*  换零钱  
    人民币有100、50、10、5、2、1、0.5、0.2、0.1等多种面额。在找零钱的时候，会有多种方案，例如需找零钱68.90元，至少有以下方案：  
    (1)1张50、1张10、1张5、3张1、1张0.5、2张0.2  
    (2)1张50、1张10、1张5、3张1、1张0.5、4张0.1  
    (3)6张10、1张5、3张1、1张0.5、2张0.2

--------------------

*  AC

#include <bits/stdc++.h>
    using namespace std;
    #define maxn 10
    int parvalue[maxn]={ 10000,5000,2000,1000,500,200,100,50,20,10};
    int num[maxn]={ 0};
    int exchange(int n){ 
    	int i,j;
    	for(i=0;i<maxn;i++){ 
    		if(n>parvalue[i])
    		    break;    
    	}   //找到比 n 小的最大面额 
    	while(n>0 && i<maxn){ 
    		if(n>=parvalue[i]){ 
    			n-=parvalue[i];
    			num[i]++;
    		}
    		else if(n<10 && n>=5){ 
    			num[maxn-1]++;
    			break;
    		}else 
    		    i++;
    	}
    	return 0;
    }
    int main(){ 
    	int i;
    	float m;
    	cout<<"请输入找零的金额："<<endl;
    	cin>>m;
    	exchange((int)100*m);
    	printf("\n%.2f元零钱的组成：\n",m);
    	for(i=0;i<maxn;i++)
    		if(num[i]>0)
    		    printf("%6.2f:%d张\n",(float)parvalue[i]/100.0,num[i]);
    	system("pause");
    	return 0;
    }