# Week 1 - Knapsack Problem

Statement

There are different versions of this problem:

• Where you can have at most one version of each object,
• Where you can have at most a given number of each object, and
• Where you can have an infinite amount of each object.

We will focus on the first problem for the next sections.

# Greedy solution

Here a greedy algorithm would notice that the first object $(15,15)$ has the best value to weight ratio, so would fit one of those in the bag first. With 7 (=22-15) capacity left it would fit a single copy of the 4th object $(5,1)$ making the bag full.

This solution has a value of 16.

However, consider the solution using objects 2 and 3. This has weight 22, so in capacity but has value 18. This is 2 value higher than the greedy solution.

In summary greedy algorithm will not work for this problem.

# Dynamic programming approach (single version)

Lets define a dynamic program for the single copy Knapsack problem.

Let $K(i, b)$ be the max value using the first $0 \leq i \leq n$ objects with a bag of capacity $0 \leq b \leq B$.

The solution to the knapsack problem will then be $K(n,B)$.

To define the recursion for this problem first set the base case $K(0,b) = K(i,0) = 0$. More generically define,

The code for this program would look as follows.

from typing import List
from dataclasses import dataclass


@dataclass
class KnapsackItem:
    weight: int
    value: int


class KnapsackSolver:
    solution_array: List[List[int]]
    items: List[KnapsackItem]
    capacity: int

    def solve(self, items: List[KnapsackItem], capacity: int) -> int:
        self._setup_problem(items, capacity)
        self._setup_solution_array()
		self._fill_array()
        return self.solution_array[-1][-1]

	def _fill_array() -> None:
		for item_number in range(1, len(self.items) + 1):
            for capacity_limit in range(1, self.capacity + 1):
                self.solution_array[item_number][
                    capacity_limit
                ] = self._solve_for_single_value(item_number, capacity_limit)

    def _setup_problem(self, items: List[KnapsackItem], capacity: int) -> None:
        self.items = items
        self.capacity = capacity

    def _setup_solution_array(self) -> None:
        self.solution_array = [
            [0 for _ in range(self.capacity + 1)]
            for _ in range(len(self.items) + 1)
        ]

    def _solve_for_single_value(
	    self,
	    item_number: int,
	    capacity_limit: int)
	-> int:
        current_item = self.items[item_number - 1]  # 0-indexed
        previous_solution = self.solution_array[item_number - 1][
	        capacity_limit
        ]
        if current_item.weight > capacity_limit:
            return previous_solution
        else:
            return max(
                [
                    previous_solution,
                    self.solution_array[item_number - 1][
                        capacity_limit - current_item.weight
                    ]
                    + current_item.value,
                ]
            )


if __name__ == "__main__":
    items = [
        KnapsackItem(weight=15, value=15),
        KnapsackItem(weight=12, value=10),
        KnapsackItem(weight=10, value=8),
        KnapsackItem(weight=5, value=1),
    ]
    capacity = 22
    solver = KnapsackSolver()
    print(solver.solve(items, capacity))

Lets look at the run time of each part of this algorithm. Let $n$ be the number of coins and $B$ be the total capacity.

First _setup_problem is $O(1)$ as it is just setting variables.

Whereas _setup_solution_array fills an $(n+1) \times (B+1)$ array that takes $O(nB)$ time.

The function _solve_for_single_value does 1 check and the at worst takes the max of 2 values so is $O(1)$. This is ran $nB$ times in _fill_array giving this a run time of $O(nB)$.

Combining these we have solve has run time $O(1) + O(nB) + O(nB) = O(nB)$.

# This is not polynomial in the input size

Even though $O(nB)$ is polynomial in $n$ and $B$ - the space it takes to represent $B$ is $\log_2(B)$. If we set $\overline{B} = \log_2(B)$ then the input size is $n, \overline{B}$ and the run time of this algorithm is $O(n 2^{\overline{B}})$ which is exponential.

The Knapsack is Nondeterministic Polynomial time (NP) , meaning there is no polynomial algorithm for the knapsack problem.

# Dynamic programming approach (multi version)

# Attempt 1

We can modify what we did for the last problem to solve this problem.

Let $K(i, b)$ be the max value using the first $0 \leq i \leq n$ objects as many times as you would like with a bag of capacity $0 \leq b \leq B$.

The solution to the knapsack problem will then be $K(n,B)$.

To define the recursion for this problem first set the base case $K(0,b) = K(i,0) = 0$. More generically define,

This is a very small change and will have the same psudo-code and run time as the previous algorithm. Though there is a way to get rid of the $i$ parameter from our array.

# Attempt 2

As we can now use as many copies of which ever coin we would like we no longer need to track the coins at all.

Let $K(b)$ be the max value using all coins for a bag with capacity $0 \leq b \leq B$.

The solution to the knapsack problem will then be $K(B)$.

To define the recursion for this problem we set

This has very simple psudo code

Knapsack Repeat (w_1, ..., w_n, v_1, ..., v_n, B)
for b = 0 -> B
	k(b) = 0
	for i = 1 -> n
		if w_i <= b
			k(b) = max(k(b), v_i + k(b-w_i))
return k(B)

The run time of the algorithm is still $O(nb)$ but it’s spacial complexity has reduced.

# Tracing the solution

You can alter the algorithm to store a second array $S$ which tracks the coin that was added to the solution to get the new optimum. Then by back tracking and subtracting the weight you will rebuild the set of coins.

# Further question

From Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.