9
\$\begingroup\$

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.

Wikipedia for more information

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)

Optimal answers required

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.

\$\endgroup\$
  • \$\begingroup\$ sandbox \$\endgroup\$ – Christopher Apr 13 '18 at 17:37
  • \$\begingroup\$ Can we assume that no object will have non-positive mass? \$\endgroup\$ – HyperNeutrino Apr 13 '18 at 17:40
  • \$\begingroup\$ @HyperNeutrino one sec removing for edits \$\endgroup\$ – Christopher Apr 13 '18 at 17:46
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – user48543 Apr 13 '18 at 17:59
  • 5
    \$\begingroup\$ The title is misleading. Due to negative weights this is not the knapsack problem but a variation on the linear programming problem. \$\endgroup\$ – ngn Apr 13 '18 at 19:19
2
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.