File Knapsack.h

↰ Parent directory (ADS/optimization)

The 0-1 knapsack of section 13.6: n objects of profit p_i and volume v_i, positive integers, and a knapsack of capacity C; a set S of volume at most C and largest profit.

Definition (ADS/optimization/Knapsack.h)

Detailed Description

DP[ i ][ c ], the best profit of the first i objects in capacity c, is :math:` -infty ` if c < 0, 0 if i = 0 or c = 0, and :math:` max{ DP[ i - 1 ][ c ] , DP[ i - 1 ][ c - v_{i-1} ] + p_{i-1} } ` otherwise. The volumes here may also be 0, and then the column c = 0 follows the same maximum instead of being 0.

knapsack() fills the table bottom up in Theta( n C ) time and reads the set back; zaino() is the memoization of the book, top down, which solves only the subproblems it reaches, in a hash table per object, of key c, rather than in a table of n C places, whose initialization alone would cost Theta( n C ); so any capacity up to the largest long is allowed. Either is pseudopolynomial: C takes log C bits of the input.

The contracts [see File Contract.h]: profits and volumes of the same objects, none negative, and the capacity not negative; the objects of knapsack() fit and give the profit found. The operations are defined in Knapsack.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 13.6, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions