Description

Assignment #3
maximize subject to
where vi > 0, wi > 0, and xi ∈{0,1} for 1 ≤ i ≤ n.
Devise a dynamic programming algorithm to solve this problem.
Your write-up should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of your write-up should provide the following:
1. A description of the algorithm in English and pseudocode.
2. At least one worked example to show how your algorithm works.
3. A proof (or argument) the algorithm is correct.
4. An analysis of the running time of the algorithm.
For example, if the knapsack capacity is 10 and we have 4 objects with values 7, 2, 8, and 11 with weights 2, 3, 2, and 12. The file looks like this:
10 4
7 2
2 3
8 2
11 12
Program submission:
See the class web page for “How to submit programs”.
Program evaluation:
See the “Program evaluation worksheet” for programming assignments on the course web page. Your program must meet all of these criteria in order to receive full credit.
1