题 13.硬币找零问题中要求找给客户最少的硬币。 coins 存储可用硬币规格,单位为角,假设规格都小于10 角,且一定有1角规格。 amount 为要找零的金额,约定必须为1角的整数倍。输出为每种规格及其数量,按规格从大到小输出,如果某种规格不必要,则输出为0。下面是其实现代码,相关说法正确的是( )。
const int MAX_COINS = 10;
int result[MAX _COINS]={0}; // 假设最多10种面额
int find coins(const vector<int>& coins, int amount){
sort(coins.begin(),coins.end(),greater<int>());
int n= coins.size();
for(int i=0;i<n; ++i){
int coin= coins[i];
int num=amount /coin;
result[i]= num;
amount -= num*coin;
if(amount ==0)break;
}
cout<<"找零方案如下:"<<endl;
for(int i=0;i<n; ++i){
cout<<sorted_coins[i]<<"角需要"<<result[i]<<"枚"<< endl;
}
return 0;
}
上述代码采用贪心算法实现
针对本题具体要求,上述代码总能找到最优解
上述代码采用枚举算法
上述代码采用分治算法