Due: Monday, June 24.
Text, problem 15.2-1 (page 338) in the second edition, or problem problem 16.1-1 (page 308) in the first edition.
Describe a dynamic programmming algorithm for the following problem. The input to the problem has two parts.
The first part is a tree that describes a company hierarchy, with the president at the top. There is a node of the tree for each employee. The children of a node V are the employees whom V directly supervises.
The second part is a table giving a conviviality rating for each employee. The rating is a nonnegative integer. This indicates how much the person will enhance a party.
The algorithm must solve the following optimization problem. The goal is to select a subset of the employees to invite to a party. It is required that, if employee V is invited to the party, then none of the employees that V directly supervises can also be invited. (In terms of the tree, the algorithm must select a collection of nodes in the tree such that no two adjacent nodes are both selected.)
The goodness of a solution is the sum of the conviviality ratings of all of the selected employees. Among all possible solutions, the algorithm must produce one that has the highest possible goodness. (You want to have the best possible party.) If there are several equally good solutions, the algorithm can produce any of those equally good solutions.
Your algorithm is not required to give the set of employees to invite, but must say what the goodness of the best solution is. (You will find that, if you can calculate that, finding the actual set of employees to invite involves a minor modification. Don't bother to do that modification.) Give a clear description of how the algorithm works.
Hint. Dynamic programming tends to work by sweeping over data structures. So it has similarities with scan algorithms, but works on data structures instead of just on lists. What decision do you need to make about each employee? What should you remember about each node in the tree? Should you sweep up the tree or down?
The 0-1 Knapsack Problem is as follows. The input consists of
Think of it as follows. You have a collection of n objects. The i-th object has size si and value vi. (If it is a diamond, it has a small size but a large value. If it is a bale of hay it has a large size and a low value. The sizes and values can be mixed in any way, but you must have one size and one value for each object.) You are a thief, and you have a knapsack that can hold a total capacity of K. You must put objects into the knapsack whose total value is as large as possible, without putting more total size into the knapsack as will fit.
More precisely, you want to select an index set I that is a subset of {1,...,n}, telling which objects to select, so that the sum of the sizes of the selected objects is no more than K, and the sum of the values of the selected object is as high as possible.
The problem is to devise a dynamic programming algorithm for this problem. To do this, you need to choose appropriate intermediate values to compute. For each j and m let Cj,m be the size of the smallest subset of the first j objects whose total value is exactly m. If there is no such subset, use a size of infinity.
For example, suppose that the size list is 3,7,4,10, and the value list is 5,6,5,5. (The first object has size 3 and value 5, etc.) If you restrict attention to just the first object, then you have two choices: put it into the knapsack or leave it out. If you put it in the knapsack, your total size is 3 and your value is 5. So C1,5 = 3. If you leave the first item out, you get a size of 0 and a value of 0. So C1,0 = 0. C1,2 = infinity, since there does not exist a subset of the first 1 objects whose total value is exactly 2. To repeat, Cj,m is the total size of the smallest subset of the first j items whose total value is exactly m. For this same input, C4,10 = 7 since there is a subset of the first 4 objects whose total value is 10 and whose total size is 7 (pick the first and third objects), and that is the smallest set that has total value 10.
Write equations that define the Cj,m values. The equations should be recursive.
Describe an algorithm to solve the 0-1 knapsack problem. You will need to compute the C values. What is the maximum value that you need to use?
How long does your algorithm take, to within a constant factor? Express your result in terms of n and the sum V of all of the values in the value list.