Python program for "0-1 knapsack problem"

Question

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 = [[0] * (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 values.

Here is an example output,

(220, 50, [2, 1])
knapsack() Time: 54.669268087000006 

NOTE - 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.

Answer 1

The code is well written in terms of style and readability, there is only a few things we could improve there.

The algorithm is also optimal for runtime, but the memory usage/allocation could be improved a little which could speed things up.

Readability

• Variable naming: some of the variables are not very descriptive:

  • grid which represents the dynamic-programming array, it needs a comment either way but maybe best_value is better.

  • items usually means the actual array, since it represents the count, it's better to name it items_count. Actually, this variable is not needed since the function could use len(weights) or len(values)

• You could use a named-tuple (or just tuple) to group the item weights and values.

Algorithm

• You can reduce the 2d array to a 1d array saving the values for the current iteration. For this to work, we have to iterate capacity (inner for-loop) in the opposite direction so we that we don't use the values that were updated in the same iteration (you can try the other way and see what goes wrong).

Incorporating these changes we get the following code:

from collections import namedtuple
from timeit import timeit

Item = namedtuple('Item', ['value', 'weight'])

def knapsack(capacity, items):
    # A DP array for the best-value that could be achieved for each weight.
    best_value = [0] * (capacity + 1)
    # The previous item used to achieve the best-value for each weight.
    previous_item = [None] * (capacity + 1)
    for item in items:
        for w in range(capacity, item.weight - 1, -1):
            value = best_value[w - item.weight] + item.value
            if value > best_value[w]:
                best_value[w] = value
                previous_item[w] = item

    cur_weight = capacity
    taken = []
    while cur_weight > 0:
        taken.append(previous_item[cur_weight])
        cur_weight -= previous_item[cur_weight].weight

    return best_value[capacity], taken

items = [Item(60, 10), Item(100, 20), Item(120, 30)]
capacity = 50

print(knapsack(capacity, items))
print('knapsack() Time: ' + str(
      timeit('knapsack(capacity, items)', 
             setup = 'from __main__ import knapsack, capacity, items')))

This change resulted in a good improvement in runtime. On my machine, it decreased the execution time (1,000,000 iterations) from 37s to 24s.