目前的纸币系统包含5种纸币,为1元、5元、16元、23元和33元,输入要购买物品的价格n为1~99元的整数,则购买该价格的物品最少需要几张纸币呢?分别给出穷举法和贪心算法的结果

本关任务:目前的纸币系统包含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;
}

当然这只是穷举,并不是最简。
如果使用动态规划的话会简便很多。