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
- The files have combined size at most W.
- 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
- Partition the problem into sub-problems.
- Solve the sub-problems.
- 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:
- 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.
- 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.
- Bottom-up computation: Compute the value of an optimal solution in a bottom-up fashion by using a table data structure.
- Construction of optimal solution: Construct an optimal solution from computed information.
- 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.