分布

Question

は（リットルで）異なる容量を持つ3つの容器であります多くの可能性があり、そこに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)) 

このアルゴリズムは、3つ以上の容器にも使用できます。しかしこれはより効率的にすることができます。重複計算を減らすために、何らかの形式のメモや動的プログラミングを使うことができますが、3つのコンテナはそれほど問題になりません。

（もちろん、これは、水が唯一1リットルの倍数に分割することができることを前提としている。）

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出力iは1 あろう。e）のコンテナが複数回使用することができます場合は、

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