0-1 Knapsack Problem

Problem:
A thief robbing a store finds \(n\) items; the \(i\)th item is worth \(v_i\) dollars and weights \(w_i\) pounds, where \(v_i\) and \(w_i\) are integers. He wants to take as valuable a load as possible, but he can carry at most \(W\) pounds in his knapsack for some integer \(W\). Which items should he take?

Analysis:
There are two versions of this problem: fractional knapsack problem and 0-1 knapsack problem.

1. Fractional knapsack problem: the items can be broken into smaller pieces, and the thief can take fractions of items.
2. 0-1 knapsack problem: the items may not be broken into smaller pieces, and the thief must decide whether to take an item or leave it (binary choices).

For fractional knapsack problem, greedy algorithm exists and the problem can be solved in \(O(n\log n)\) time based on sorting. And a better approach may take \(O(n)\) time for the worst case based on linear-time SELECT algorithm.

For 0-1 knapsack problem, no greedy algorithm exists and we need turn to dynamic programming approach. The algorithm will take \(O(nW)\) time.

Solution:
Define \(c[i,w]\) to be the optimal value for items \(1,2,...,i\) and maximum weight \(w\). There are following recursive relations:
\[c[i,w]=\begin{cases}0, & i=0\text{ or }w=0\\c[i-1,w], & w_i\gt w\\ \max\{v_i+c[i-1,w-w_i], c[i-1,w]\}, & i>0 \text{ and }w_i \le w\end{cases}\] We can have the pseudocode:

DP_01_Knapsack(value, weight, W)
   assert value.length = weight.length
   n ← value.length
   for w ← 0 to W:
      c[0,w] ← 0
   for i ← 1 to n:
      c[i,0] ← 0
      for w ← 1 to W:
         c[i,w] ← c[i-1,w]
         if weight[i] ≤ w and value[i]+c[i-1,w-weight[i]] > c[i-1,w]:
            c[i-1,w] ← value[i]+c[i-1,w-weight[i]]

The set of items to take can be deduced from the table, starting at \(c[n,W]\) and tracing backwards where the optimal values came from. If \(c[i,w]=c[i-1,w]\), then item \(i\) is not part of the solution, and we are continue tracing with \(c[i-1,w]\). Otherwise item \(i\) is part of the solution, and we continue tracing with \(c[i-1,w-w_i]\).

References:

Dynamic Programming Solution to the 0-1 Knapsack Problem

A More Efficient Algorithm for Longest Increasing Subsequence

Problem:
Given an array of numbers or a string of length \(n\), find a longest increasing subsequence.
In my previous post, I discussed the dynamic programming approach with time complexity \(O(n^2)\). For this specific problem, we can have a more efficient algorithm which is also based on dynamic programming. Please see Wikipedia for reference.

The algorithm uses only arrays and binary searching. It processes the sequence elements in order, maintaining the longest increasing subsequence found so far. Denote the sequence values as \(X[1]\), \(X[2]\), etc. Then, after processing \(X[i]\), the algorithm will have stored values in two arrays:

\(M[j]\) — stores the position \(k\) of the smallest value \(X[k]\) such that there is an increasing subsequence of length \(j\) ending at \(X[k]\) on the range \(k ≤ i\) (note we have \(j ≤ k ≤ i\) here).

\(P[k]\) — stores the position of the predecessor of \(X[k]\) in the longest increasing subsequence ending at \(X[k]\).

In addition the algorithm stores a variable \(L\) representing the length of the longest increasing subsequence found so far.

Note that, at any point in the algorithm, the sequence \[X[M[1]], X[M[2]], ..., X[M[L]]\] is nondecreasing. For, if there is an increasing subsequence of length \(i\) ending at \(X[M[i]]\), then there is also a subsequence of length \(i-1\) ending at a smaller value: namely the one ending at \(X[P[M[i]]]\). Thus, we may do binary searches in this sequence in logarithmic time.

The algorithm, then, proceeds as follows.

L = 0
for i = 1, 2, ... n:
   binary search for the largest positive j ≤ L 
     such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
   P[i] = M[j]
   if j == L or X[i] < X[M[j+1]]:
      M[j+1] = i
      L = max(L, j+1)

The result of this is the length of the longest sequence in \(L\). The actual longest sequence can be found by backtracking through the \(P\) array: the last item of the longest sequence is in \(X[M[L]]\), the second-to-last item is in \(X[P[M[L]]]\), etc. Thus, the sequence has the form \[..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].\]
Because the algorithm performs a single binary search per sequence element, its total time can be expressed using Big \(O\) notation as \(O(n\log n)\).


References:

Wikipedia item: longest increasing subsequence

Related Posts:

\(O(n^2)\) Algorithm for Longest Increasing Subsequence

Longest Increasing Subsequence

Problem:
Given an array of numbers or a string of length \(n\), find a longest increasing subsequence.

Brute-force approach:
Enumerate all possible subsequences and then determine which are increasing and store the longest one. This approach is obviously impractical for large \(n\) and its time complexity is exponential.

Dynamic programming approach:
The longest increasing subsequence of an array \(A\) of length \(n\) can be determined based on that of all the prefix arrays. We need use an auxiliary array \(T[n]\), in which \(T[i]\) stores the length of longest increasing (non-decreasing) subsequence ending at \(A[i]\). Notice that is ending at, i.e., the last element must be \(A[i]\). Meanwhile, the global maximum length is also stored in variable \(L\). The time complexity for this algorithm will be \(O(n^2)\).



Related Posts:

\(O(n\log n)\) Algorithm for Longest Increasing Subsequence