knapsack

knapsack Problem

0–1 knapsack problem

Given weights and values of \(n\) items, put these items in a knapsack of capacity \(W\) to get the maximum total value in the knapsack.

\(f(i, j):\) using only first \(i\) items, with maximum capacity of \(j\), the maximum total value you can get.

Then, we can write our base cases:

• \(f(0, :) = 0\)
• \(f(:, 0) = 0\)

0 items have values 0 and no items can be put into knapsack with capacity of 0.

At \(f(i, j)\), comparing it to \(f(i - 1, j)\), we can choose to include item \(i\) or not. So, we can write out of transition function \(f(i, j)\):

1. If there is still extra capacity for item \(i\) with total capacity \(j\) (i.e \(sum(weights[: i + 1]) \leq j)\)), then we can just simply add values of item \(i\). \[f(i, j) = f(i - 1, j) + values(i)\]

2. If there is no extra capacity for item \(i\) at \(j\) and the current weight \(weight[i] > j\), then we only need to keep the previous maximum values because the item \(i\) won't fit whatsoever: \[f(i, j) = f(i - 1, j)\]

3. If there is no extra capacity for item \(i\) at \(j\) but \(weight[i] \leq j\), then we can choose to include this item and discard some past items, or move on without considering this item:

   1. The total values if we include this item (\(\text{current value } + \text{ The maximum value we can get after we fill the capacity j with i}\) (we need to exclude the current item)): \[\text{total}_{include} = values[i] + f(i - 1, j - weights[i])\]

   2. The maximum value exclude current item: \[f(i - 1, j)\]

   By taking the maximum over these two, we have:

   \[f(i, j) = \max(f(i - 1, j), \; values[i] + f(i - 1, j - weights[i]))\]

Unbounded knapsack problem

Given a knapsack weight \(W\) and a set of \(n\) items with certain value \(v_i\) and weight \(w_i\), we need to calculate the maximum amount that could make up this quantity exactly. This is different from classical Knapsack problem, here we are allowed to use unlimited number of instances of an item.

\(f(i, j):\) using only first \(i\) items, with maximum capacity of \(j\), the maximum total value you can get.

Then, we can write our base cases:

• \(f(0, :) = 0\)
• \(f(:, 0) = 0\)

0 items have values 0 and no items can be put into knapsack with capacity of 0.

At \(f(i, j)\), comparing it to \(f(i - 1, j)\), we can choose to include item \(i\) or not. So, we can write out of transition function \(f(i, j)\):

1. If there is still extra capacity for item \(i\) with total capacity \(j\) (i.e \(sum(weights[: i + 1]) \leq j)\)), then we can just simply add values of item \(i\). \[f(i, j) = f(i - 1, j) + values(i)\]

2. If there is no extra capacity for item \(i\) at \(j\) and the current weight \(weight[i] > j\), then we only need to keep the previous maximum values because the item \(i\) won't fit whatsoever: \[f(i, j) = f(i - 1, j)\]

3. If there is no extra capacity for item \(i\) at \(j\) but \(weight[i] \leq j\), then we can choose to include this item and discard some past items, or move on without considering this item:

   1. The total values if we include this item (\(\text{current value } + \text{ The maximum value we have can get after we fill the capacity j with i}\) (we need to include the current item)): \[\text{total}_{include} = values[i] + f(i, j - weights[i])\]

   2. The maximum value exclude current item: \[f(i - 1, j)\]

   By taking the maximum over these two, we have:

   \[f(i, j) = \max(f(i - 1, j), \; values[i] + f(i, j - weights[i]))\]