分布的水在三个容器

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