c++写小猴装桃（调度问题简化版 模板题） 时间限制 : 2.000 sec 内存限制 : 128 MiB 题目描述 小猴到了一个桃园，发现了n堆桃子，每堆桃子有ai个，每个桃子的体积为1。小猴只能带两个容量相同的袋子，请问小猴带的袋子最小容量是多少才能把n堆桃子全部装走？注意，小猴只会将同一堆的桃子装入到同一个袋子中。 这题要注意剪枝。 输入 测试样例由多组测试数据组成。 每个样例包含两行，第一行输入1个正整数n； 第二行输入n个整数ai。 1 <= n <= 30，1 <= ai <= 1000 输出 对每个测试例，输出一行，表示结果。

以下是C++代码实现，使用了贪心算法：

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 35;
int n, a[maxn];

bool dfs(int u, int x, int y) {
    if (u == n) { // 所有桃子都装完了，返回true
        return true;
    }
    if (a[u] > x && a[u] > y) { // 如果当前桃子堆的桃子数大于两个袋子的容量，则返回false
        return false;
    }
    if (a[u] <= x && dfs(u + 1, x - a[u], y)) { // 如果当前桃子堆的桃子数小于等于第一个袋子的容量，尝试将它放入第一个袋子
        return true;
    }
    if (a[u] <= y && dfs(u + 1, x, y - a[u])) { // 如果当前桃子堆的桃子数小于等于第二个袋子的容量，尝试将它放入第二个袋子
        return true;
    }
    return false; // 如果尝试了所有情况，都不能将当前桃子堆装入袋子，则返回false
}

int main() {
    while (cin >> n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            sum += a[i];
        }
        sort(a, a + n, greater<int>()); // 将桃子堆按照桃子数从大到小排序
        int ans = sum;
        for (int i = a[0]; i <= sum / 2; i++) { // 枚举第一个袋子的容量
            if (sum - i <= i) { // 剪枝：第二个袋子不需要比第一个袋子的容量大
                if (dfs(0, i, sum - i)) { // 尝试将所有桃子都装入两个袋子中
                    ans = i; // 记录当前最小容量
                    break; // 找到最小容量，则退出循环
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

思路说明：

1. 将桃子堆按照桃子数从大到小排序，这样可以先尝试将桃子数多的桃子堆装入袋子，以便节省空间。
2. 枚举第一个袋子的容量，从第一个桃子堆的桃子数到所有桃子堆桃子数的和的一半，这样可以保证第一个袋子的容量不超过所有桃子堆桃子数的一半，以便节省空间。
3. 在dfs函数中，将当前桃子堆尝试放入第一个袋子和第二个袋子，如果都不能放下，则返回false。
4. 在dfs函数中，如果当前桃子堆已经被装入袋子，则跳过它，尝试装下一个桃子堆。如果所有桃子堆都装完了，则返回true，表示所有桃子都能被装入两个袋子中。
5. 在dfs函数中，为了减少搜索时间，如果当前桃子堆的桃子数大于两个袋子的容量，则返回false，这是一个剪枝操作。

希望能够帮助到您！