0
正の重み（必ずしも整数ではない）と対応する等価長（1xN）のリストを考えてみると、所与の合計Sと正確に合計し、最も低いコスト（重みリストのサブセットに対応するコスト*重みの合計）を有する重みリスト。 Pythonで書かれているのは、他の言語ではそれほど良いことではないので、（可能であれば）ベストだろう！コストが最も低い部分集合を求めるアルゴリズム
例：
w = [2.5, 3.0, 1.0, 5.5] # Weight list
c = [1.0, 1.5, 2.0, 3.0] # Cost list
S = 6.5 # Target sum
この場合、私たちのSに合計二つの可能なサブセットがあります。これらのサブセットの
sub1 = [2.5, 3.0, 1.0]
sub2 = [1.0, 5.5]
のコストは、次のとおりサブセット1は
cost1 = 2.5*1.0+3.0*1.5+1.0*2.0 = 9.0
cost2 = 1.0*2.0+5.5*3.0 = 18.5
最低コスト（9.0）があります。これは、私が望むサブセットです。
可能な解決策は、すべての可能な組み合わせを計算してから、計算されたコストの最小値を選ぶことです。私は、この問題に対するより効率的な解決策があることを期待していました。
私はさまざまなソリューションを検索していますが、私は、同じコストの問題を解決し、同時に最低コストを得ることのできないPythonのソリューションしか見つけることができませんでした。このようなソリューションの例を次に示します。Algorithm to find which number in a list sum up to a certain number
体重は少なくともプラスになっていますか？いずれにしても、これは単一の等価制約を持つ非常に直接的な0-1整数線形計画問題です。したがって、ブランチ・アンド・バウンド・アルゴリズムのようなものは機能しますが、より簡単なアプローチがあります。動的プログラミングは確かに自然な方法です。何を試しましたか？ –
これを参照するには、サブセットサム問題https://en.m.wikipedia.org/wiki/Subset_sum_problemと呼ばれ、効率的な解決法が存在しないと広く考えられています。 （もちろん、効率的な解決策を求めているのではなく、ただの解決策を求めています） – Cruncher
私は質問を更新しました。はい、重みは正の実数です。私は少なくとも可能なすべての組み合わせをチェックするよりも効率的なものを望んでいます。 – sheg