本关任务:目前的纸币系统包含5种纸币,为1元、5元、16元、23元和33元,输入要购买物品的价格n为1~99元的整数,则购买该价格的物品最少需要几张纸币呢?分别给出穷举法和贪心算法的结果
编程要求
根据提示,在右侧编辑器补充代码,用户输入物品价格n,计算并输出2个结果,分别代表穷举法的结果和贪心法的结果
从大到小贪心。
#include <bits/stdc++.h>
using namespace std;
int n,m,cnt;
int main(){
cin>>n;
while(n>=33){
n-=33;
cnt++;
}
while(n>=23){
n-=23;
cnt++;
}
while(n>=16){
n-=16;
cnt++;
}
while(n>=5){
n-=5;
cnt++;
}
while(n>=1){
n-=1;
cnt++;
}
cout<<cnt;
return 0;
}
当然这只是穷举,并不是最简。
如果使用动态规划的话会简便很多。