红、绿、蓝三色球装包最大可装数量求解与算法优化

现有r个红球、g个绿球、b个蓝球，以及无限个包装袋，要求每个包装袋恰好装3个球，且袋中球至少包含2种不同颜色，求最多可以装满多少个包装袋？

你提供的动态规划方案逻辑上可以得到正确结果，但存在三个核心缺陷：

• 状态空间为O(rgb)，当r、g、b数值较大时，状态数量指数级增长，性能会急剧下降
• 实现细节存在冗余：代码中连续两次对packets(r-2,g-1,b)+1取最大值，属于无效计算
• 用multiset作为缓存key，插入、查找的额外开销较高

这个问题可以通过数学推导直接得到O(1)时间复杂度的解法，无需动态规划：

1. 首先将三个数量从小到大排序，记为a ≤ b ≤ c
2. 我们可以得到两个必然成立的最大装袋数上界：
   • 上界1：所有球的总数除以3，即(a + b + c) // 3，因为每个袋子必须装3个球，总数量不可能超过该值
   • 上界2：较小两个数的和，即a + b，因为每个合法袋子最多装2个数量最多的球c，所以每个袋子至少要消耗1个a或b，用完a和b之后就不可能再装出合法袋子
3. 最终的最大装袋数就是两个上界的最小值，即min((a + b + c) // 3, a + b)

正确性证明 #

• 情况1：如果c ≤ 2*(a + b)，此时(a + b + c) // 3 ≤ a + b，我们可以通过优先装1a1b1c的组合，剩余球调整为2个同色+1个其他色的组合，刚好凑到总和除以3的袋子数，不会出现剩余全同色的情况
• 情况2：如果c > 2*(a + b)，此时a + b < (a + b + c) // 3，我们可以给每个a和b搭配2个c装袋，刚好消耗完所有a和b，得到a + b个合法袋子，剩余的c全为同色无法再装袋，是最优解

#include <algorithm>
using namespace std;

long long packets(long long r, long long g, long long b) {
    long long nums[] = {r, g, b};
    sort(nums, nums + 3);
    long long sum = nums[0] + nums[1] + nums[2];
    return min(sum / 3, nums[0] + nums[1]);
}

注：使用long long类型是为了避免三个数求和时出现整数溢出问题。

内容的提问来源于stack exchange，提问作者kumarp