Sluggish Knapsack X59240

Statement

html

We consider the classical Knapsack problem in its 0/1 variant; this means that each object is either taken fully into the knapsack, exactly once, or left fully out.

More precisely, given are a weight limit limw and a sequence of n objects consisting of weight and value of each object. Here n is a non-negative integer, and all the other values are positive integers. Solutions are subsets (rather, more precisely, subsequences) of objects whose sum of weights is at most limw and whose sum of values is as large as possible: one such solution is to be returned.

Thus, you are asked to write a function knapsack(weights, values, n, limw) that returns a list of integers less than n corresponding to objects whose total weight is at most limw and whose total value is as large as possible. The first two arguments are sequences of positive integers storing the information regarding each of the n objects.

Note that there may be instances where the answer is an empty list, when no better solution is possible (recall that the sum of an empty list is zero).

Observation

Sometimes, there will be several solutions: your function may return any solution that fulfills the given conditions. On the other hand, the time allowance of this problem is rather mild, and even quite inefficient solutions may be accepted (hence the "sluggish" adjective).

Sample session

>>> weights =  [7, 8, 3]
>>> values =  [3000, 4000, 2000]
>>> print(sum(values[obj] for obj in knapsack(weights, values, 3, 10)))
5000
>>> weights =  [7, 8, 3]
>>> values =  [3000, 6000, 2000]
>>> print(sum(values[obj] for obj in knapsack(weights, values, 3, 10)))
6000
>>> weights =  [1, 1, 1, 1]
>>> values =  [3, 5, 7, 7]
>>> print(sum(values[obj] for obj in knapsack(weights, values, 4, 2)))
14

Information

Author: José Luis Balcázar
Language: English
Official solutions: Python
User solutions: Python