The knapsack problem is a problem in combinatorial optimization: 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. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where there are financial constraints, such as finding the least wasteful way to cut raw materials, or deciding on a selection of investments and portfolios.

The most common problem being solved is the 0-1 knapsack problem, which restricts the number x[i] of copies of each kind of item to zero or one. Given a set of n items numbered from 0 up to n-1, each with a weight w[i] and a profit p[i], along with a maximum weight capacity M, we need to maximize sum(p[i]*x[i] for i in range(n)), subject to sum(w[i]*x[i] for i in range(n)) <= M and x[i] in {0,1}. Here x[i] represents the number of instances of item i to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack’s capacity.

In the rational knapsack problem selecting only a part of objects is allowed.

Assignment

Write a Python function knapsack which takes the capacity M of the knapsack as parameter, as well as a list of weights and a list of profits. The function returns the total profit and the total weight of the optimal selection, together with a list of selected objects sorted on the index of the original list (for each selected object its index in the original list of weights/profits in which ratio the objects is contained in the optimal selection).

Example

>>> w1 = [86.0, 44.0, 83.0, 52.0, 76.0, 97.0, 83.0, 49.0, 77.0, 72.0]
>>> p1 = [803.0, 305.0, 413.0, 778.0, 851.0, 949.0, 957.0, 420.0, 719.0, 913.0]
>>> M1 = 500.0
>>> knapsack(M1, w1, p1)
(5568.5, 500.0, [(0, 0.5), (3, 1.0), (4, 1.0), (5, 1.0), (6, 1.0), (8, 1.0), (9, 1.0)])

>>> w2 = [54.0, 99.0, 77.0, 48.0, 10.0, 61.0, 31.0, 30.0, 90.0, 100.0]
>>> p2 = [624.0, 518.0, 982.0, 323.0, 811.0, 112.0, 209.0, 473.0, 432.0, 195.0]
>>> M2 = 250.0
>>> knapsack(M2, w2, p2)
(3422.0, 250.0, [(0, 1.0), (2, 1.0), (3, 1.0), (4, 1.0), (6, 1.0), (7, 1.0)])