File KnapsackVariants.h

↰ Parent directory (ADS/optimization)

The relatives of the knapsack in which an item can be taken many times, and the counting versions of the knapsack, all solved by the dynamic programming on the capacity of section 13.3, in pseudopolynomial time:

Definition (ADS/optimization/KnapsackVariants.h)

Detailed Description

  • rodCutting(): a rod of length L sold in pieces, price[ t - 1 ] the price of a piece of length t, the largest gain :math:` R[ l ] = max_{1 leq t leq min( l , m )} price[ t - 1 ] + R[ l - t ] `, R[ 0 ] = 0, with the pieces read back; O( L m ) time and O( L ) space for m prices;

  • unboundedKnapsack(): the largest profit of objects of volumes v and profits p in unlimited supply in a knapsack of capacity C, :math:` P[ c ] = max( P[ c - 1 ] , max_{v_i leq c} P[ c - v_i ] + p_i ) `, and how many copies of each object; O( n C ) time, O( C ) space;

  • minValueExactWeight(): the least value of coins of weights w and values v in unlimited supply that weigh exactly W, nothing if no such coins exist; with all the values 1 it is the fewest coins of the change (optimalChange() of File CoinChange.h); O( n W ) time, O( W ) space;

  • coinChangeWays(): the number of ways of paying T with coins of the given values in unlimited supply, the order not counting: the coins enter one value at a time, :math:` N[ x ] mathrel{+}= N[ x - d ] ` for x from d up, so that each multiset is counted once; O( n T ) time, O( T ) space;

  • subsetSumCount(): the number of subsets of places of A of sum k, the same scan with x going down, each item used at most once; O( n k ) time, O( k ) space;

  • minimumSquares(): the fewest squares of positive integers that sum to n. The dynamic programming :math:` S[ i ] = 1 + min_{t^2 leq i} S[ i - t^2 ] ` takes :math:` Theta( n sqrt{n} ) ` time; number theory answers in :math:` O( sqrt{n} ) : 0 for n = 0, 1 for a square, 4 for :math: n = 4^a ( 8 b + 7 ) ` (Legendre’s three-square theorem), 2 if :math:` n - t^2 ` is a square for some t, 3 otherwise; at most 4 by Lagrange’s four-square theorem. Taking the largest square first is not optimal: 18 = 9 + 9, not 16 + 1 + 1.

The running times are pseudopolynomial, exponential in the size of the numbers: the 0-1 decision versions are NP-complete [see File Pseudopolynomial.h]. The bounded knapsack, each object available b_i times, reduces to the 0-1 one by splitting b_i in powers of two, and the counting versions are the coefficients of the generating functions :math:` prod_d ( 1 - z^d )^{-1} ` and :math:` prod_i ( 1 + z^{a_i} ) `.

The contracts [see File Contract.h]: the capacities and the amounts are not negative, the volumes, the weights and the values of the coins positive, the items of subsetSumCount() not negative; the pieces of rodCutting() and the copies of unboundedKnapsack() fit and give the value found. The functions are defined in KnapsackVariants.tpp.

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

    1. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, section 14.1

  1. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, chapters 3 and 5

    1. Rabin, J. O. Shallit, Randomized algorithms in number theory, Communications on Pure and Applied Mathematics 39(S1), S239-S256, 1986, doi:10.1002/cpa.3160390713

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions