The Knapsack Problem (0-1 Knapsack)

Informal description

We have computed n data files that we want to store, and we have only W available bytes of storage.

"File i has size wi bytes and takes vi minutes to re-compute."

We want to avoid as much recomputing as possible, so we want to find a subset of files to store such that

  1. The files have combined size at most W.
  2. The total computing time of the stored files is as large as possible.

Note: We can’t store parts of files, it is either the whole file or nothing (which is why it is called 0-1 knapsack).

Question: How should we choose the files?

Formal description of 0-1 knapsack Problem

Given: Two n-tuples of positive numbers

and we wish to determine the subset (of files to store) that

maximizes (which is our goal)

subject to (which is our constraint or condition).

Remark: This is an optimization problem.

Solution 1: Brute force technique

Try all 2n possible subsets T. Choose the best one.

Running time for a brute force solution is exponentially high. Therefore, we need a better solution.

Solution 2: Divide-and-conquer

  1. Partition the problem into sub-problems.
  2. Solve the sub-problems.
  3. Combine the solutions to solve the original one.

Remark: If the sub-problems are not independent, i.e. sub-problems share sub-sub-problems, then a divide-and-conquer algorithm repeatedly solves the common sub-sub-problems. Thus, it does not work efficiently!

So we need a solution that is better than the divide-and-conquer approach.

How about dynamic programming (DP)?

Solution 3: Dynamic programming

Definition: Dynamic programming is a method for solving optimization problems.

The idea: Compute the solutions to the sub-sub-problems once and store the solutions in a table, so that later they can be reused repeatedly (the concept of memorization).

Remark: We trade space for time.

Steps to develop a DP algorithm are as follows:

  1. Structure: Characterize the structure of an optimal solution. Decompose the problem into smaller problems, and find a relation between the structure of the optimal solution of the original problem and the solutions of the smaller problems.
  2. Principle of optimality: Recursively define the value of an optimal solution. Express the solution of the original problem in terms of optimal solutions for smaller problems.
  3. Bottom-up computation: Compute the value of an optimal solution in a bottom-up fashion by using a table data structure.
  4. Construction of optimal solution: Construct an optimal solution from computed information.

Note that:

  • Steps 3 and 4 may often be combined.
  • Steps 1–3 form the basis of a dynamic-programming solution to a problem.
  • Step 4 can be omitted if only the value of an optimal solution is required.

 The next post will discuss the implementation of a DP algorithm.

comments powered by Disqus