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.

Improve this question
8
  • 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? Commented Mar 7, 2017 at 13:44
  • For reference this is known as the subset sum problem 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) Commented Mar 7, 2017 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. Commented Mar 7, 2017 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 Commented Mar 7, 2017 at 13:55
  • 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. Commented Mar 7, 2017 at 15:39

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.