2

重みの合計が指定された重み W と正確に等しいセット内の重み付き要素のすべての可能な組み合わせを見つけたいと思います

{ 'A', 'B', 'C', 'D', 'E' }セットwhereweights = {'A':2, 'B':1, 'C':3, 'D':2, 'E':1}およびから k 個の要素を選択したいとしますW = 4。

次に、これは次のようになります。 ('A','B','E') ('A','D') ('B','C') ('B','D','E') ('C','E')

強引な方法は、指定されたセットのすべての順列を ( を使用してitertools.permutations) 見つけ、最初の k 個の要素を W の重み付き合計でスプライスすることだと認識しています。しかし、私はセットごとに少なくとも 20 個の要素を扱っています。高い。

ナップザックのバリアントを使用すると、重みのみ (値ではなく) が考慮され、重みの合計がW (劣っていない)に等しくなければならない場合に役立つと思います。

これをPythonで実装したいのですが、cs理論のヒントがあれば役立ちます。エレガンスにボーナスポイント！

4

3 に答える 3

3

すべてのnをループする! 順列は非常に高価です。代わりに、すべての 2^ nサブセットを生成します。

from itertools import chain, combinations

def weight(A):
    return sum(weights[x] for x in A)

# Copied from example at http://docs.python.org/library/itertools.html
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in xrange(len(s) + 1))

[x for x in powerset({'A', 'B', 'C', 'D', 'E'}) if weight(x) == W]

収量

[('A', 'D'), ('C', 'B'), ('C', 'E'), ('A', 'B', 'E'), ('B', 'E', 'D')]

これは、リスト内包表記の戻り部分を に変更するか、 in の呼び出しをtotuple(sorted(x))に置き換えることで、ソートされたタプルに変換できます。listpowersetsorted

于 2011-11-04T14:11:33.407 に答える
1

そのようなセットのアイテム数に上限はありますか? 実行し、最大でも約 40 である場合、Knapsack の Wikipedia ページで説明されている「meet-in-the-middle」アルゴリズムは非常に単純であり、ブルート フォース計算よりも大幅に複雑さが低くなります。

注: Python dict よりもメモリ効率の高いデータ構造を使用すると、これはより大きなセットでも機能する可能性があります。効率的な実装では、サイズ 60 のセットを簡単に処理できます。

実装例を次に示します。

from collections import defaultdict
from itertools import chain, combinations, product

# taken from the docs of the itertools module
def powerset(iterable):
     "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
     s = list(iterable)
     return chain.from_iterable(combinations(s, r) for r in xrange(len(s) + 1))

def gen_sums(weights):
    """Given a set of weights, generate a sum --> subsets mapping.

    For each posible sum, this will create a list of subsets of weights
    with that sum.

    >>> gen_sums({'A':1, 'B':1})
    {0: [()], 1: [('A',), ('B',)], 2: [('A', 'B')]}
    """
    sums = defaultdict(list)
    for weight_items in powerset(weights.items()):
        if not weight_items:
            sums[0].append(())
        else:
            keys, weights = zip(*weight_items)
            sums[sum(weights)].append(keys)
    return dict(sums)

def meet_in_the_middle(weights, target_sum):
    """Find subsets of the given weights with the desired sum.

    This uses a simplified meet-in-the-middle algorithm.

    >>> weights = {'A':2, 'B':1, 'C':3, 'D':2, 'E':1}
    >>> list(meet_in_the_middle(weights, 4))
    [('B', 'E', 'D'), ('A', 'D'), ('A', 'B', 'E'), ('C', 'B'), ('C', 'E')]
    """
    # split weights into two groups
    weights_list = weights.items()
    weights_set1 = dict(weights_list[:len(weights)//2])
    weights_set2 = dict(weights_list[len(weights_set1):])

    # generate sum --> subsets mapping for each group of weights,
    # and sort the groups in descending order
    set1_sums = sorted(gen_sums(set1).items())
    set2_sums = sorted(gen_sums(set2).items(), reverse=True)

    # run over the first sorted list, meanwhile going through the
    # second list and looking for exact matches
    set2_sums = iter(set2_sums)
    try:
        set2_sum, subsets2 = set2_sums.next()
        for set1_sum, subsets1 in set1_sums:
            set2_target_sum = target_sum - set1_sum
            while set2_sum > set2_target_sum:
                set2_sum, subsets2 = set2_sums.next()
            if set2_sum == set2_target_sum:
                for subset1, subset2 in product(subsets1, subsets2):
                    yield subset1 + subset2
    except StopIteration: # done iterating over set2_sums
        pass
于 2011-11-04T15:12:27.770 に答える
0

これを（ある程度）効率的に行う秘訣は、最初のk個のアイテムを使用して同じ重みを持つ要素のセットを作成することです。

k = 0の空集合から始めて、k-1の組み合わせを使用してkの組み合わせを作成します。負の重みを持つことができない限り、合計重みがWより大きい組み合わせを整理することができます。

これがあなたの例を使ってどのように実行されるかです：

comb [k、w]は、最初のk個の要素を使用した総重みwを持つ要素のセットです。
中括弧はセットに使用されます。
S + eは、Sの各メンバーに要素eを追加することによって作成されたセットのセットです。

comb[0,0]={}
comb[1,0]={comb[0,0]}
comb[1,2]={comb[0,0]+'A'}
comb[2,0]={comb[1,0]}
comb[2,1]={comb[1,0]+'B'}
comb[2,2]={comb[1,2]}
comb[2,3]={comb[1,2]'B'}
comb[3,0]={comb[2,0]}
comb[3,1]={comb[2,1]}
comb[3,2]={comb[2,2]}
comb[3,3]={comb[2,3],comb[2,0]+'C'}
comb[3,4]={comb[2,3]+'C'}
comb[4,0]={comb[3,0]}
comb[4,1]={comb[3,1]}
comb[4,2]={comb[3,2],comb[3,0]+'D'}
comb[4,3]={comb[3,3],comb[3,1]+'D'}
comb[4,4]={comb[3,4],comb[3,2]+'D'}
comb[5,0]={comb[4,0]}
comb[5,1]={comb[4,1],comb[4,0]+'E'}
comb[5,2]={comb[4,2],comb[4,1]+'E'}
comb[5,3]={comb[4,3],comb[4,2]+'E'}
comb[5,4]={comb[4,4],comb[4,3]+'E'}

答えはcomb[5,4]で、これは次のように単純化されます。

{
  {{'B'}+'C'},
  {{'A'}+'D'},
  {
    {{'A'}+'B'},
    {'C'},
    {'B'}+'D'             
  }+'E'
}

すべての組み合わせを与える。

于 2011-11-04T14:58:59.003 に答える