23.2 复杂购买决策问题

“当购买选择涉及三种或更多物品时，”我继续解释道，”问题的复杂度会大大增加，需要我们设计更复杂的嵌套循环结构。”

23.2.1 购买文具

题目描述：新学年就要开始了，爸爸把N元钱给了小青，让他购买一批文具，并作了以下要求：只能买圆珠笔、铅笔和铅笔芯，并且每样至少买一支，总数要超过30支，而且钱要全部花完。当小青去到文具店时，发现圆珠笔8角钱一支、铅笔2角钱一支、铅笔芯1角钱一支。小青怎么买才能符合爸爸的要求呢？请你编个程序帮他算出符合购买要求的所有方案总数。

样例输入：

30

样例输出：

17

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n, cnt = 0;
    cin >> n;                   // 读取总金额（单位：元）
    n = n * 10;                 // 将元转换为角（便于计算）
    
    for(int i = 1; i <= (n - 2 - 1) / 8; i++) {  // i是圆珠笔的数量，至少买1支，最多买(n-3)/8支（预留铅笔和铅笔芯各1支）
        int m = n - i * 8;      // 买完圆珠笔后剩余的钱
        for(int j = 1; j <= (m - 1) / 2; j++) {  // j是铅笔的数量，至少买1支，最多买(m-1)/2支（预留铅笔芯至少1支）
            int k = m - j * 2;  // 计算剩余钱数，全部用来买铅笔芯
            if(k % 1 == 0 && k >= 1) {  // 判断剩余钱数能否整除铅笔芯单价（总是为真），且至少买1支铅笔芯
                int total = i + j + k;  // 计算购买的总支数
                if(total > 30) {        // 判断总支数是否超过30
                    cnt++;              // 累加有效方案数
                    // cout << i << " " << j << " " << k << endl;  // 输出具体方案（用于调试）
                }
            }
        }
    }
    
    cout << cnt;                // 输出方案总数
    return 0;
}

思考：

• 这个问题涉及三种物品，需要使用三重循环或两重循环加计算
• 注意单位的转换：题目中金额单位是元，而物品单位是角，需要统一
• 由于铅笔芯价格最低，可以用剩余的钱全部购买铅笔芯，减少一层循环
• 在计算方案数时，需要确保总支数超过30，并且每种文具至少购买一支

23.2.2 百钱百鸡问题

题目描述：这是一个古老的数学问题：鸡翁（公鸡）一，值钱x；鸡母（母鸡）一，值钱y；鸡雏（小鸡）z，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？现在，我们将这个问题一般化：n钱买m只鸡，公鸡、母鸡和小鸡的价格分别是x、y和z，请求出所有可能的方案数。

样例输入：

100 5 3 1 100 100

样例输出：

4

代码实现：

#include <iostream>
using namespace std;

int main() {
    int x, y, z, n, m;
    cin >> n >> x >> y >> z >> m >> m;  // 读取总金额n、公鸡单价x、母鸡单价y、小鸡单价z、总数量m（注意：m被重复输入）
    int cnt = 0;                // 初始化方案计数器
    
    for(int i = 0; i <= n / x; i++) {  // i是公鸡的数量，从0开始，最多买n/x只
        int s1 = n - x * i;     // 计算买完公鸡后剩余的钱
        for(int j = 0; j <= s1 / y; j++) {  // j是母鸡的数量，从0开始，最多买s1/y只
            int s2 = s1 - y * j;  // 计算买完母鸡后剩余的钱
            if(s2 % z == 0) {   // 判断剩余钱数是否能整除小鸡单价
                int k = s2 / z;  // 计算能买的小鸡数量
                if(i + j + k == m) {  // 判断总数量是否等于m
                    cnt++;       // 累加有效方案数
                    // cout << i << " " << j << " " << k << endl;  // 输出具体方案（用于调试）
                }
            }
        }
    }
    
    cout << cnt;                // 输出方案总数
    return 0;
}

思考：

• 百钱百鸡是一个经典的数学问题，这里进行了一般化处理
• 使用双重循环遍历公鸡和母鸡的数量，然后计算小鸡的数量
• 关键条件是总价钱为n，总数量为m
• 注意处理整除的情况，确保小鸡数量为整数