$30.00
Description
This set of questions focus on dynamic programming.
1. Knapsack without repetitions. Consider the following knapsack problem:
The total weight limit W = 10 and
Item 
Weight 
Value 
1 
6 
$30 
2 
3 
$14 
3 
4 
$16 
4 
2 
$9 
Solve this problem using the dynamic programming algorithm presented in class (Feb 7th). Please show the two dimensional table L(w; j) for w = 0; 1; :::; W and j = 1; 2; 3; 4.
2. Give a dynamic programming algorithm for the following task.
Input: A list of n positive integers a_{1}; a_{2}; : : : ; a_{n} and a number t.
Question: Does some subset of the a_{i}‘s add up to t? (You can use each a_{i} at most once.)
The running time should be O(nt).
Consider the subproblem L(i; s), which returns the answer of \Does a subset of a_{1}; :::; a_{i} sum up to s?”.
Below are some substeps that will help you develop your algorithm.
a What are the two options we have regarding item i toward answering the subproblem L(i; s)?

For each of the option, how would it change the subproblem? More speci cally, what happens to the target sum and what happens to the set of available integars?

Based on the answers to the previous two questions, write a recursive formula that expresses L(i; s) using the solutions to smaller subproblems.

Provide pseudocode for the dynamic programming algorithm that builds the solution table L(i; s) and returns the correct answer to the nal problem.


Modify the pseudocode such that it will not only return the correct \yes”, \no” answer, but also return the exact subset if the answer is \yes”.


6.2

6.3

6.8
1