0. Problem

Assume there are several items needs to be thrown into a knapsack, while the space of knapsack is limited. Also, we need to maximize the value of the whole batch of the items.

1. Greedy Algorithms

Idea 1

More items is best, start with small ones and take as many as you can

Idea 2

Valuable items are best, start with the most valuable items

Idea 3

Value density. That is dollars per kilogram.

Advantages

• quick to design and implement
• can be very fast

Problems

• no quality guarantees
• quality can vary widely on the input
• problem feasibility needs to be easy

2. Dynamic Programming

Basic principle

• divide and conquer
• bottom up computation

Notations and Conventions

$O(k, j)$ denotes the optimal solution to the knapsack problem with capacity $k$ and items $[1 … j]$

$$\begin{aligned}
&\text{max.}\quad \sum_{i \in 1 . . j} v_{i} x_{i} \\
&\text{subject to}\quad \sum_{i \in 1 . . j} w_{i} x_{i} \leq k \\
&x_{i} \in\{0,1\} \quad(i \in 1 . . j)
\end{aligned}$$

We are interested in finding out the best value $O(K, n)$

Bellman Equations

Assume that we know how to solve $O(k, j-1)$ for all $k$ in $0… K$

We want to solve $O(k, j)$ which is just with one more item

If $w_j \le k$, there are 2 cases

• Either we do not select item $j$, then the best solution we can obtain is still $O(k, j-1)$
• Or we select it and the best solution is $v_j + O(k-w_j, j-1)$

then

• $ O(k, j) = \max(O(k, j-1), v_j + O(k-w_j, j-1)) $ if $ w_j \le k$
• $ O(k, j) = O(k, j-1) $ otherwise

Of course

• $O(k, 0) = 0 $ for all $k$

int O(int k,int j) {
   if (j == 0)
       return 0;
   else if (wj <= k)
       return max(O(k,j-1),vj + O(k-wj,j-1)); 
   else
       return O(k,j-1)
}

What is the complexity of this algorithm

• time to fill the table $O(k*n)$

3. Branch and Bound

• branching: split the problem into a number of subproblems
• bounding: find an optimistic estimate of the best solution to the subproblem
  maximization: upper bound
  minimization: lower bound

4. Search Strategies

Branch and Bound

– Search Strategies: depth-fisrt, best-first, least-discrepancy

Depth-first

Best-first

Least-Discrepancy