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