Unbounded knapsack problem (UKP)

Catalogue of combinatorial problems · Knapsack problems · Catalogue (PDF)

Definition 1: Unbounded knapsack problem

Given:

1. a knapsack of capacity \(c \in \Z_{\ge 1}\),

2. a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items,

3. for each item \(j \in \mathscr{I}\), which is available in an unlimited number of copies, a profit \(p_j \in \Z_{\ge 1}\) and a weight \(w_j \in \Z_{\ge 1}\),

the Unbounded Knapsack Problem (UKP) asks to decide how many copies of each item to insert into the knapsack, so that the total weight of all selected item copies does not exceed the knapsack capacity and the total profit of all selected item copies is maximized.

Assumptions

• We make the following assumptions:

  1. The total weight of all possible copies of all items (up to the maximum number that can fit in the knapsack) exceeds the knapsack capacity (otherwise, all copies could be selected). Formally:

     \[ \sum_{j \in \mathscr{I}} \hat b_j \, w_j > c \]

  2. Each item individually fits into the knapsack (otherwise, it cannot be selected). Formally:

     \[ w_j \le c, \qquad \forall j \in \mathscr{I} \]

What the course does on this problem

Technique	Where
Definition	Ch. 2 «Knapsack problems»
Formulations	Ch. 9 «Formulations of knapsack problems»
Dynamic programming	Ch. 16 «Principles of dynamic programming»; Ch. 18 «DP for the unbounded knapsack problem»; Ch. 27 «DP for the coin change problem»; Ch. 28 «DP for the rod cutting problem»
Exercises	Exercise 2.3; Exercise 9.8; Ch. 18 (5 exercises)