0

Given one (1xN) list of positive weights (not necessarily integers i.e. floats) and an equaled-length (1xN) list of corresponding costs I want to find the subset of the weight list that sums exactly to a given sum S and has the lowest cost (sum of costs*weights corresponding to the subset in the weight list). Written in Python would be best (if possible) since I am not that good with other languages!

Example: 

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

For this case we have two possible subsets that sums to S:

sub1 = [2.5, 3.0, 1.0]
sub2 = [1.0, 5.5]

The costs of these subsets are: 

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

Since subset 1 has the lowest cost (9.0) this is the subset I want.

One possible solution would of course be to calculate all possible combinations and then just pick the minimum of the calculated costs. I was hoping that there is a more efficient solution to this problem.

I have search for different solutions but I could only find solutions for Python which solve the problem of equal sum and not simultaneously getting the lowest cost. Here is an example of such a solution: Algorithm to find which number in a list sum up to a certain number.

Community
  • 1
  • 1
sheg
  • 1
  • 3
  • Are the weights at least positive? In any event, this is a very straightforward 0-1 integer linear programming problem with a single equality constraint. Thus things like the branch-and-bound algorithm will work, though there might be simpler approaches. Dynamic programming is certainly a natural way to go. What have you tried? – John Coleman Mar 07 '17 at 13:44
  • For reference this is known as the subset sum problem https://en.m.wikipedia.org/wiki/Subset_sum_problem and is widely believed that no efficient solution to it exists. (Of course you're not asking for an efficient solution, just a solution) – Cruncher Mar 07 '17 at 13:46
  • I updated the question. Yes, weights are positive real-valued. I am hoping for something at least more efficient than checking all possible combinations. – sheg Mar 07 '17 at 13:51
  • @sheg if you look at the Wikipedia page I linked, it explains the most efficient algorithms we currently know. You can't expect to do better than them. You just need to modify it a little to test possible solutions against your weights. Should be a rather trivial modification – Cruncher Mar 07 '17 at 13:55
  • @Cruncher Thanks for the suggestion! For me it seems like the Wikipedia page you provided does not take into account the "cost aspect" of the problem. So what you mean is to used the solution proposed in the Wikipedia link to fin all possible subsets and then find the subset with the lowest cost? – sheg Mar 07 '17 at 15:38
  • 1
    Where's your work? Time for you to follow up on Cruncher's research. I will note that even though your data is not integers, you can open up some options by using integers anyway. The OP can be expressed as exact integers, or you can use an epsilon. – Kenny Ostrom Mar 07 '17 at 15:39
  • @sheg the cost aspect is a very small part of the problem. It's very possible that the algorithm will produce the lowest cost since the array is sorted by cost anyway, but I'm not overly familiar with the specifics of the algorithm. You need to just think about the problem and how you can modify it to fit your guarantee. The added cost doesn't add any computational complexity to the problem. You just need to be clever about it. The addition of the costs was most likely to just make it harder for you to google a solution to the problem – Cruncher Mar 07 '17 at 15:54
  • @Cruncher Okey, good for me to know that it does not add complexity with the costs since this is really not my field and for me it could as well been essential for the algorithm. I will give my best try at the problem, thanks – sheg Mar 07 '17 at 19:31

1 Answers1

0

I finally solved the problem using binary integer programming as suggested by John Coleman. Here is the code: https://github.com/sebastianheg/knapsack-problem.

sheg
  • 1
  • 3