# +- knapsack problem

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

For example you can be given a max weight of 15 and objects with value/masses as [5,2], [7,4] [1,1] and you would output [7,0,1] which is 7 [5 <value>, 2 <mass>] objects and 1 [1 <value>, 1 <mass>] object for a score of 36.

# Rules

Input can be taken in any reasonable format

Output is also flexible format,

You may not use libraries that are non-standard. If you have to install or download any library to use it separate from the initial setup then it is not allowed

Objects may have negative mass and value (i.e -1,-1)

# Winning

Shortest code wins

# Negative mass and value?

This is a key part of this challenge. Lets say you have a object with items (mass, value) such as [4,3],[-1,-1] and a bag with capacity of 15. You could put 3 of the first ones and score 9 or put 4 of the first ones and one of the -1,-1 object for a score of 11.

• sandbox Apr 13, 2018 at 17:37
• Can we assume that no object will have non-positive mass? Apr 13, 2018 at 17:40
• @HyperNeutrino one sec removing for edits Apr 13, 2018 at 17:46
• Can we assume everything is an integer? Also, will we have to deal with cases like [[2, 1], [-1, -1]] where the total value can be made arbitrarily large?
– user48543
Apr 13, 2018 at 17:59
• The title is misleading. Due to negative weights this is not the knapsack problem but a variation on the linear programming problem.
– ngn
Apr 13, 2018 at 19:19

# Pyth, 18 bytes

h.MshMZfghQseMTy*F


Outputs as a list of [value, weight] pairs. Horrendously inefficient, but it is NP-complete.
Try it here

### Explanation

h.MshMZfghQseMTy*F
y*FQ  Get all sets with up to <capacity> of each item.
fghQseMT      Choose the sets whose total weight fits in the bag.
.MshMZ              Choose those with the highest value.
h                    Take the first.