# The Knapsack Problem (0-1 Knapsack)

## by

## 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 w _{i} bytes and takes *

*v*

_{i}*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 2^{n }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.

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.