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.

Improve this question
\$\endgroup\$
11
  • \$\begingroup\$ sandbox \$\endgroup\$
    – user63187
    Commented Apr 13, 2018 at 17:37
  • \$\begingroup\$ Can we assume that no object will have non-positive mass? \$\endgroup\$
    – hyperneutrino ♦
    Commented Apr 13, 2018 at 17:40
  • \$\begingroup\$ @HyperNeutrino one sec removing for edits \$\endgroup\$
    – user63187
    Commented Apr 13, 2018 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
    Commented Apr 13, 2018 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
    Commented Apr 13, 2018 at 19:19

1 Answer 1

Reset to default
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.
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.