0
給定一個（1xN）正權重列表（不一定是整數，即浮點數）和相等成本的等長列表（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]
這些子集的費用是：
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
由於子集1成本最低（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