最少纸币数量：穷举法与贪心算法比较

#include using namespace std;

int main() { int n; int minNumOfNotes = INT_MAX; // 初始化最小纸币数量为最大整数 int greedyNumOfNotes = 0; // 初始化贪心算法得到的纸币数量为0

cin >> n; // 输入要购买物品的价格

// 穷举法
for(int e = 0; e <= n/33; e++){
    for(int d = 0; d <= n/23; d++){
        for(int c = 0; c <= n/16; c++){
            for(int b = 0; b <= n/5; b++){
                int a = n - 33*e - 23*d - 16*c - 5*b;
                if(a >= 0 && b >= 0 && c >= 0 && d >= 0 && e >= 0)
                {
                    int totalNotes = a + b + c + d + e; // 计算纸币总数
                    if(totalNotes < minNumOfNotes)
                    {
                        minNumOfNotes = totalNotes; // 更新最小纸币数量
                    }
                }
            }
        }
    }
}

// 贪心算法
int a1=33, a2=23, a3=16, a4=5, a5=1;
int b1=0, b2=0, b3=0, b4=0, b5=0;
if(n >= a1)
{
    b1 = n / a1;
    n %= a1;
}
if(n >= a2)
{
    b2 = n / a2;
    n %= a2;
}
if(n >= a3)
{
    b3 = n / a3;
    n %= a3;
}
if(n >= a4)
{
    b4 = n / a4;
    n %= a4;
}
if(n >= a5)
{
    b5 = n;
}
greedyNumOfNotes = b1 + b2 + b3 + b4 + b5; // 计算贪心算法得到的纸币数量

cout << "穷举法结果：" << minNumOfNotes << endl;
cout << "贪心算法结果：" << greedyNumOfNotes << endl;

return 0;

}