分佈的水在三個容器

Question

給出的是三個容器具有不同容量（以升）：

答：11

B：8

C：5

的問題是如何許多可能性在那裏分配13升對他們？ 我試圖通過列舉他們所有的系統性蠻力，並得出了51種可能性的結果。

有沒有蠻力的另一種方式？而且我的解決方案是否正確？

在此先感謝！ ：d

Answer 1

你可以嘗試這樣的：

• 如果你只有一個容器，所有的水都必須進入那個容器
• ，如果你有一個以上的容器，把任何金額，適合到第一容器中，並與剩餘的水的溶液和容器

結合可以實現這個作爲一個簡單的遞歸算法（這裏用Python）：

def divide(liters, containers): 
    if len(containers) == 1 and containers[0] >= liters: 
     yield [liters] 
    elif len(containers) >= 2 and liters <= sum(containers): 
     first, *rest = containers 
     for x in range(0, min(liters, first) + 1): 
      for remaining in divide(liters - x, rest): 
       yield [x] + remaining 

result = list(divide(13, [11, 8, 5])) 
print(len(result)) 

該算法也可用於三個以上的容器。不過，這可以變得更有效率。您可以使用某種形式的記憶或動態編程來減少重複計算，但對於三個容器無關緊要。

（當然，這假定水只能被劃分成一升的倍數。）

Answer 2

假設，

1. 單個容器可僅使用一次。
2. 一個容器只能充滿。

的想法是回溯

存儲在list容器的容量。

由於沒有指定語言標記，我會用C++語言給我。組合的總數存在於answer變量中，並且containers使用的是存儲在result變量中的列表列表。

int answer = 0; 
vector<vector<int>> result; 
void fillJug(vector<int> list, int index, int cap, vector<int> temp) 
{ 
    if(cap == 0) 
    { 
     ++answer; 
     result.push_back(temp); 
     return; 
    } 
    if(cap < list[index]) 
    { 
     return; 
    } 
    for(int i= index; i < list.size(); ++i) 
    { 
     vector<int> newtemp(temp); 
     newtemp.push_back(list[i]); 
     fillJug(list,i + 1,cap - list[i], newtemp); 
    } 
} 

集裝箱[5, 8, 11]和總容量= 13的輸出將是1。 我。E）採用[5, 8]

如果容器可以使用多個時間再改

fillJug(list,i + 1,cap - list[i], newtemp); 

到

fillJug(list,i,cap - list[i], newtemp);