Here is what a knapsack/rucksack problem means (taken from Wikipedia):
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.
With reference to - https://en.wikipedia.org/wiki/Knapsack_problem - this is the definition of a 0-1 knapsack or a 0-1 rucksack problem:
Here is my version of the "0-1 knapsack problem" in python:
def knapsack(capacity, items, weights, values): grid = [ * (capacity + 1)] for item in range(items): grid.append(grid[item].copy()) for k in range(weights[item], capacity + 1): grid[item + 1][k] = max(grid[item][k], grid[item][k -weights[item]] + values[item]) solution_value = grid[items][capacity] solution_weight = 0 taken =  k = capacity for item in range(items, 0, -1): if grid[item][k] != grid[item - 1][k]: taken.append(item - 1) k -= weights[item - 1] solution_weight += weights[item - 1] return solution_value, solution_weight, taken
NOTES - The total weight of the taken items cannot exceed the capacity of the knapsack. The total weight of the items in the knapsack is called “solution weight”, and their total value is the “solution value”.
Here are some example input values,
values = [60, 100, 120] weights = [10, 20, 30] capacity = 50 items = len(values) print(knapsack(capacity, items, weights, values)) print('knapsack() Time: ' + str(timeit.timeit('knapsack(capacity, items, weights, values)', setup = 'from __main__ import knapsack, capacity, items, weights, values')))
where my budget ($
50) is the sack’s
capacity, the shares are the
items to be packed, the current prices are the
weights and the price estimates are the
Here is an example output,
(220, 50, [2, 1]) knapsack() Time: 54.669268087000006
knapsack() Time is in milliseconds.
So I would like to know whether I could make this code shorter and more efficient.
Any help would be highly appreciated.