最大数据包数

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;
}

我的解决方案may be在逻辑上是正确的，但是对于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⌋包。