找零钱.txt

来自「里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等」· 文本 代码 · 共 37 行

//有1，2，5三种硬币
#include <iostream> 
#include <vector> 
using namespace std; 

int  change_money(vector<int> &ivec, int n) 
{ 
	ivec.push_back(0) ; //0分钱就不需要找 
    ivec.push_back(1) ; //1分钱只需要1个硬币 
    ivec.push_back(1) ; //2分钱只需要1个硬币 
    ivec.push_back(2) ; //3分钱需要2个硬币 
    ivec.push_back(2) ; //4分钱需要2个硬币 
    ivec.push_back(1) ; //5分钱需要1个硬币 
    for(int i=6;i<=n;++i) 
	{ 
		int tmp1 = 1+ivec[i-1] ; 
        int tmp2 = 1+ivec[i-2] ; 
        int tmp5 = 1+ivec[i-5] ; 
        int tmp = tmp1 < tmp2 ? tmp1:tmp2; 
        tmp = tmp<tmp5 ? tmp:tmp5; 
        ivec.push_back(tmp); 
	} 
    return  ivec[i-1]; 
} 

int main() 
{ 
   cout << "请输入要找的零钱数: " ; 
   int n; 
   cin >> n; 
   vector<int> ivec; 
   cout << "最少需要的硬币数为:" << change_money(ivec,n); 
   cout << endl; 
   return 1 ;
}