3

プログラミングパズルの1つを解くのに非常に苦労しています。アイテム（i＃で示される）とアイテムの価格としての値を含む辞書があります。`アイテムを組み合わせてコンボパッケージを形成できます。

{('i2', 'i3'): '4', ('i1',): '1',('i1', 'i3', 'i4'): '6.5', ('i3',): '3',('i1', 'i2', 'i3'): '4.5', ('i2',): '2', ('i4',): '4'}

指定された入力アイテムの最低価格を返したい。コンボパッケージから最低価格で追加アイテムを入手した場合、ユーザーは問題ありません。

  1. 入力i1の場合、価格1を返す必要があります（これはすべてのi1アイテムの最低価格です）
  2. 入力（i1、i2）の場合、3を返す必要があります。
  3. 入力（i1、i2、i3、i4）の場合、8.5を返す必要があります
  4. 入力（i1、i1、i2、i3、i4）の場合、9.5を返す必要があります

誰かがそれをどのように進めるかについて何か考えがありますか？どのアルゴリズムを使用しますか？

ありがとう、Sunil

4

1 に答える 1

2

itertools.combinations（）を使用して、xパッケージの組み合わせを生成します。次に、それぞれの組み合わせに必要なアイテムが含まれているかどうかを確認し、最低価格で有効なコンボを見つけます。

アイテムの4つの異なるパッケージのすべての組み合わせを見つけるには：

d = {('i2', 'i3'): '4', ('i1',): '1',('i1', 'i3', 'i4'): '6.5', ('i3',): '3',
     ('i1', 'i2', 'i3'): '4.5', ('i2',): '2', ('i4',): '4'}
from itertools import combinations
combos = list(combinations(d, 4)) # you should try combos of different lenghts, 
                                  # from 1 to the number of desired items

説明のために、コンボの1つを見てみましょう。print combos[0]与える：
(('i2', 'i3'), ('i1',), ('i1', 'i3', 'i4'), ('i3',))

そして、このコンボの価格を取得するには：

sum([float(d[item]) for item in combos[0]])

これは14.5を与えます

最も安い適切なコンボを見つけるのはあなたに任せます:)

于 2012-11-29T18:40:35.990 に答える