有 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 與最大資料包的一些模式，但無法從邏輯上證明它們。有人可以幫我解決他們的想法嗎？
謝謝
uj5u.com熱心網友回復：
不失一般性，通過排列顏色假設 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? 包，按要求。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/321243.html
上一篇：運算子多載矩陣乘法