找到等于成本最低的总和的子集的算法
Algorithm to find subset that is equal to sum with lowest cost
给定一个 (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.
我终于按照 John Coleman 的建议使用二进制整数规划解决了这个问题。这是代码：https://github.com/sebastianheg/knapsack-problem。
给定一个 (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.
我终于按照 John Coleman 的建议使用二进制整数规划解决了这个问题。这是代码：https://github.com/sebastianheg/knapsack-problem。