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

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

标签： c++algorithm

Answer 1

Assume without loss of generality that r ≥ g ≥ b by permuting the colors. The answer is at most ⌊(r+g+b)/3⌋ because every packet needs 3 balls. The answer is at most g+b because every packet needs a green ball or a blue ball. It turns out that the answer is equal to the minimum of these two quantities (so without the assumption, min((r+g+b)/3, r+g, r+b, g+b) assuming truncating division as in C++).

We form b packets with one blue ball and two of whichever of red or green has more balls remaining, or one of each if they’re tied. After these packets, let r′ be the number of red balls remaining and g′ be the number of green balls remaining. If r′ > 2g′ and there are at least three balls remaining, then we cannot have used any green balls yet, and we hit our quota of g+b by packing them with two red balls each. Otherwise, we form packets with either two red balls and one green ball or one red ball and two green balls so as to leave less than three balls, which means that we have formed ⌊(r+g+b)/3⌋ packets, as required.