我如何为这个 "balls and boxes" 类似背包的问题创建一个贪心算法？
How can I create a greedy algorithm for this "balls and boxes" knapsack-like problem?
假设有n个球，每个球的重量最多为1。我们可以假设这些球的重量放在数组W[1..n]中，其中0 <= W[i] <= 1 代表所有 i。问题是把这些球放在最少数量的盒子里，使得每个盒子里装的球不超过两个，并且每个盒子里放的球的总重量<=1.
我要为此设计一个高效的贪心算法。我认为一个明显的选择（选择最大的第一个和最小的第二个）是不正确的。但是，如果我首先选择最大的可用球，然后选择第二个最大的剩余球呢？我认为这是对的，但我不确定如何证明这一点。这样做会产生一个简单的 O(n^2) 算法。
这似乎也是背包问题的某种变体，但贪心算法不是最优的。
贪婪算法的常用证明模板是证明算法的前 k 个选择可以扩展到最优解，对于所有 k ≥ 0 通过对 k 的归纳。事实证明，你的两个想法都是正确的，每一个贪婪算法都是正确的，它重复地将最大的剩余球与（如果可能的话）任何将与它一起去的球放在一个盒子里。
归纳的基本情况 k = 0 是微不足道的。对于这一步，考虑一个与前 k−1 个框的贪婪解一致的最优解。让 B 成为不在前 k-1 个盒子中的最重的球。贪心将 B 装进盒子#k。考虑一下可能性。
如果box#k出现在最优解中，则后者满足归纳所需要的条件
如果贪心解有B自己在一个盒子里，那么B不适合任何剩余的球，所以最优解也有B自己，前k个决策一致。
如果greedy有B和另一个球，optimal只有B，那么我们可以通过将另一个球移到B的盒子来修改最优解。这个新解也是最优的，满足归纳的条件。
如果贪心和最优的B有不同的球，那么我们可以交换最优解中的那些球，使其与贪心解对齐。我们知道这是可能的，因为另一个盒子里的球不能比 B 大，因为可能比 B 大的 k−1 在两个解决方案中的包装方式相同。
您的第二个解决方案可以使用平衡二叉搜索树在 O(n log n) 时间内实现。
假设有n个球，每个球的重量最多为1。我们可以假设这些球的重量放在数组W[1..n]中，其中0 <= W[i] <= 1 代表所有 i。问题是把这些球放在最少数量的盒子里，使得每个盒子里装的球不超过两个，并且每个盒子里放的球的总重量<=1.
我要为此设计一个高效的贪心算法。我认为一个明显的选择（选择最大的第一个和最小的第二个）是不正确的。但是，如果我首先选择最大的可用球，然后选择第二个最大的剩余球呢？我认为这是对的，但我不确定如何证明这一点。这样做会产生一个简单的 O(n^2) 算法。
这似乎也是背包问题的某种变体，但贪心算法不是最优的。
贪婪算法的常用证明模板是证明算法的前 k 个选择可以扩展到最优解，对于所有 k ≥ 0 通过对 k 的归纳。事实证明，你的两个想法都是正确的，每一个贪婪算法都是正确的，它重复地将最大的剩余球与（如果可能的话）任何将与它一起去的球放在一个盒子里。
归纳的基本情况 k = 0 是微不足道的。对于这一步，考虑一个与前 k−1 个框的贪婪解一致的最优解。让 B 成为不在前 k-1 个盒子中的最重的球。贪心将 B 装进盒子#k。考虑一下可能性。
如果box#k出现在最优解中，则后者满足归纳所需要的条件
如果贪心解有B自己在一个盒子里，那么B不适合任何剩余的球，所以最优解也有B自己，前k个决策一致。
如果greedy有B和另一个球，optimal只有B，那么我们可以通过将另一个球移到B的盒子来修改最优解。这个新解也是最优的，满足归纳的条件。
如果贪心和最优的B有不同的球，那么我们可以交换最优解中的那些球，使其与贪心解对齐。我们知道这是可能的，因为另一个盒子里的球不能比 B 大，因为可能比 B 大的 k−1 在两个解决方案中的包装方式相同。
您的第二个解决方案可以使用平衡二叉搜索树在 O(n log n) 时间内实现。