Bounded knapsack problem (BKP)

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

Definition 1: Bounded 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}\), a profit \(p_j \in \Z_{\ge 1}\), a weight \(w_j \in \Z_{\ge 1}\), and a number of available copies \(b_j \in \Z_{\ge 1}\),

the Bounded Knapsack Problem (BKP) 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, each item is taken no more than its available copies, and the total profit of all selected item copies is maximized.

Assumptions

• We make the following assumptions:

  1. The total weight of all available copies of all items exceeds the knapsack capacity (otherwise, all copies could be selected). Formally:

     \[ \sum_{j \in \mathscr{I}} 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} \]

  3. The total weight of all available copies of any single item does not exceed the knapsack capacity (otherwise, that item could never be taken in the maximum allowed number of copies). Formally:

     \[ b_j \, 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. 19 «DP for the bounded knapsack problem»
Exercises	Exercise 2.3; Exercise 9.7; Ch. 19 (5 exercises)