Skip to content

Dynamic Programming

Different from divide-and-conquer, DP divide the problem into overlapping subproblems.

In order to have efficient solution, the number of subproblems should be polynomial.

2 Different Ways

top-down and bottom-up

Knapsack Problem

\(n\) objects, weight for each item \(w=[w_i]\), value for each item \(v=[v_i]\).

The capacity of knapsack \(W\).

Object: How to maximize the value of items such that the total weight doesn't exceed \(W\).

Find the item set \(S\) such that: \(\max\sum_{i\in S}v_i\) with constraint: \(\sum_{i\in S}w_i\leq W\).

GREEDY Algorithm doesn't work!

Dynamic Programming Idea

Let \(OPT(i,w)\) be the maximum profit with subset of item \(1,\cdots,i\) with total weight limit \(w\).

Case 1: \(OPT(i,w)\) doesn't contain item \(i\)

  • \(OPT(i,w)\) selects the best of \(1,\cdots,i-1\) using the weight limit \(w\).

Case 2: \(OPT(i,w)\) contains item \(i\)

  • It comes from \(OPT(i-1,w-w_i)+v_i\).

$$

OPT(i,w)=\begin{cases} 0\text{ if }i=0\ OPT(i-1,w)\text{ if }w_i>w\ \max{OPT(i-1,w),v_i+OPT(i-1,w-w_i)}\text{ otherwise} \end{cases}

$$

Results should be \(OPT(n,W)\)

Time complexity: \(O(n\cdot W)\). It is not polynomial! (pseudo-polynomial)

Actually Knapsack problem is NP-hard!

Local Search

For every feasible solution \(y\), the subset of feasible solutions "neighbor" to \(y\): \(neighborhood(y)\).

Idea is simple: Start from initial solution, repeatedly switch to a better solution in current neighborhood.

  1. Fix initial solution \(y\) for input \(x\).
  2. while \(\exists y'\in neighborhood(y)\) s.t. \(y'\) is better than \(y\): \(y\gets y'\).
  3. return \(y\).

In order to get polynomial time:

  1. Initialization should take polynomial time.
  2. Every iteration in while should in polynomial time.

⚠Sometimes the neighborhood may have exponential cardinality.

Local optimal VS Global optimal.

In many problems, the local optimal solution computed by local search has some approximation guarantee compared to the global optimal solution.

e.g. Max Cut, the local search guarantees at least half of the global optimal solutions.