Maximum number of packets

Question

There are r red balls, g green balls and b blue balls. Also there are infinite number of packets given to you. Each packet must be filled with only 3 balls and should contain balls of at least 2 different colors. Find the maximum number of packets that can be filled?

Here is my approach using Dynamic Programming which is straight forward

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

My solution may be logically correct but is surely inefficient for large values of r,g and b. I also identified some patterns for r,g,b vs maximum packets but cannot prove them logically. Can someone help me with their idea?.
Thank you

user_2144669 · Answer

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.

Maximum number of packets

1 Answers