最近、私はPythonで答えられるべきインタビューの質問を提出しました。量 - 値のペアのリストが与えられていれば、その合計がある提供された値に近いか、少なくともある程度大きい値である。例えば、[（1、$ 5）、（3、$ 10）、（2、$ 15）]、および所望の値36ドルの場合、答えは[（2、$ 15）、（1、 $ 10）]または[（1、$ 15）、（2、$ 10）、（1、$ 5）その理由は、$ 40が達成可能な36ドル以上の最小の合計であり、これがその合計を達成する2つの方法であるためです。Python - 数値より大きいか等しい数値の組み合わせ
私は困惑しました。誰にも解決策がありますか？
数字はあなただけのブルートフォースができるように小さい：
In []:
notes = [(1, 5), (3, 10), (2, 15)]
wallet = [n for a, b in notes for n in [b]*a]
combs = {sum(x): x for i in range(1, len(wallet)) for x in it.combinations(wallet, i)}
target = 36
for i in sorted(combs):
if i >= target:
break
i, combs[i]
Out[]:
(40, (5, 10, 10, 15))
あなただけでcombs辞書の理解を置き換え、すべての組み合わせのためにこれを拡張することができます。
combs = {}
for i in range(1, len(wallet)):
for x in it.combinations(wallet, i):
combs.setdefault(sum(x), set()).add(x)
...
i, combs[i]
Out[]:
(40, {(5, 10, 10, 15), (10, 15, 15)})
あなたは 'itertoolsを試すことができます.combinations' – Wen
与えられた数量 - 値の組み合わせのすべてを見つけて、最小のelment [s] –