c++ - 最大数据包数

Question

有 r 个红球、g 个绿球和 b 个蓝球。此外，还有无限数量的数据包提供给您。每包只能装 3 个球，并且应包含至少 2 种不同颜色的球。求出最多可以填充多少个数据包？

这是我使用动态编程的方法，非常简单

    map<multiset<int>,int> store;

int packets(int r,int g,int b){
    if (r<0||g<0||b<0){
        return 0;
    }
    if (r==g&&g==b){
        return r;
    }
    if ((r+g==0)||(g+b==0)||(b+r==0)){
        return 0;
    }
    if (r==0&&b==0&&g==0){
        return 0;
    }
    multiset<int> key;
    key.insert(r);key.insert(g);key.insert(b);
    if (store.find(key)!=store.end()){
        return store[key];
    }
    int max_packets = packets(r-2,g-1,b)+1;
    max_packets = max(max_packets,packets(r-2,g-1,b)+1);
    max_packets = max(max_packets,packets(r-1,g-2,b)+1);
    max_packets = max(max_packets,packets(r-2,g,b-1)+1);
    max_packets = max(max_packets,packets(r-1,g,b-2)+1);
    max_packets = max(max_packets,packets(r,g-2,b-1)+1);
    max_packets = max(max_packets,packets(r,g-1,b-2)+1);
    max_packets = max(max_packets,packets(r-1,g-1,b-1)+1);
    store[key] = max_packets;
    return max_packets;
}

我的解决方案可能在逻辑上是正确的，但对于较大的 r、g 和 b 值来说肯定是低效的。我还确定了 r、g、b 与最大数据包的一些模式，但无法从逻辑上证明它们。有人可以帮我实现他们的想法吗？
谢谢

Answer 1

不失一般性地假设 r ≥ g ≥ b 通过排列颜色。答案最多是 ⌊(r+g+b)/3⌋ 因为每个数据包需要 3球。答案最多是 g+b，因为每个数据包都需要一个绿球或蓝色球。事实证明，答案等于最小值这两个量(所以在没有假设的情况下，min((r+g+b)/3, r+g, r+b, g+b) 假设像 C++ 中那样截断除法)。

我们用一个蓝色球和两个红色或红色球组成 b 个包。绿色有更多的球剩余，如果平局则各一个。后这些数据包，令 r′ 为剩余红球的数量，g′ 为剩余的绿球数量。如果 r′ > 2g′ 并且至少有还剩下三个球，那么我们还不能使用任何绿球，并且我们每个人都装了两个红球，从而达到了 g+b 的配额。否则，我们用两个红球和一个绿球组成数据包或者一个红球和两个绿球，这样就剩下三个以下球，这意味着我们已经按照要求形成了 ⌊(r+g+b)/3⌋ 个数据包。