1
1.
CSCI 570 – Fall 2020 – HW6 – solution
Graded problems
From the lecture, you know how to use dynamic programming to solve the 0-1 knapsack problem where each item is unique and only one of each kind is available. Now let us consider knapsack problem where you have infinitely many items of each kind. Namely, there are n different types of items. All the items of the same type i have equal size wi and value vi. You are offered with infinitely many items of each type. Design a dynamic programming algorithm to compute the optimal value you can get from a knapsack with capacity W.
Solution: Similar to what is taught in the lecture, let OP T (k, w) be the maximum value achievable using a knapsack of capacity 0 ≤ w ≤ W and with k types of items 1 ≤ k ≤ n. We find the recurrence relation of OPT(k,w) as follows. Since we have infinitely many items of each type, we choose between the following two cases:
• Weincludeanotheritemoftypekandsolvethesub-problemOPT(k,w− vk ).
• We do not include any item of type k and move to consider next type of item this solving the sub-problem OP T (k − 1, w).
Therefore, we have
OP T (k, w) = max{OP T (k − 1, w), OP T (k, w − wk ) + vk }.
Moreover, we have the initial condition OP T (0, 0) = 0.
Given a non-empty string s and a dictionary containing a list of unique words, design a dynamic programming algorithm to determine if s can be segmented into a space-separated sequence of one or more dictionary words. If s=“algorithmdesign” and your dictionary contains “algorithm” and “design”. Your algorithm should answer Yes as s can be segmented as “algorithmdesign”.
Solution: Let si,k denote the substring sisi+1 . . . sk. Let Opt(k) denote whether the substring s1,k can be segmented using the words in the dictio- nary, namely OP T (k) = 1 if the segmentation is possible and 0 otherwise.
1
2.
A segmentation of this substring s1,k is possible if only the last word (say si . . . sk ) is in the dictionary the remaining substring s1,i can be segmented. Therefore,we have equation:
Max(Opt(i)),0 < i < k and si+1,k is a word in the dictionary Opt(k) = 0, otherwise
(1)
We can begin solving the above recurrence with the initial condition that Opt(0) = 1 and then go on to compute Opt(k) for k = 1,2,...,n. The answer corresponding to Opt(n) is the solution and can be computed in Θ(n2) time.
3. Given n balloons, indexed from 0 to n − 1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] ∗ nums[i] ∗ nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent. You may assume nums[−1] = nums[n] = 1 and they are not real therefore you can not burst them. Design an dynamic programming algorithm to find the max- imum coins you can collect by bursting the balloons wisely. Analyze the running time of your algorithm.
Solution: Here is an example. If you have the nums arrays equals [3,1,5,8]. The optimal solution would be 167, where you burst balloons in the order of 1, 5 3 and 8. The left balloons after each step is:
[3,1,5,8] → [3,5,8] → [3,8] → [8] → [] And the coins you get equals:
167 = 3 ∗ 1 ∗ 5 + 3 ∗ 5 ∗ 8 + 1 ∗ 3 ∗ 8 + 1 ∗ 8 ∗ 1.
Let OPT(l,r) be the maximum number of coins you can obtain from balloons l,l + 1,...,r − 1,r. The key observation is that to obtain the optimal number of coins for balloon from l to r, we choose which balloon is the last one to burst. Assume that balloon k is the last one you burst, then you must first burst all balloons from l to k − 1 and all the balloons from k + 1 to r which are two sub problems. Therefore, we have the following recurrence relation:
OPT(l,r)= max{OPT(l,k−1)+OPT(k+1,r)+nums[k]∗nums[l−1]∗nums[r+1]} l≤k≤r
(2)
We have initial condition OP T (l, r) = 0 if r < l. For running time anal- ysis, we in total have O(n2) and computation of each state takes O(n) time. Therefore, the total time is O(n3).
2
4. You are given a set of n types of rectangular 3-D boxes, where the ith box has height hi, width wi and depth di (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box. Following are the key points to note in the problem statement:
• A box can be placed on top of another box only if both width and depth of the upper placed box are smaller than width and depth of the lower box respectively.
• We can rotate boxes such that width is smaller than depth. For example, if there is a box with dimensions 1×2×3 where 1 is height, (2,3) is base, then there can be three possibilities, 1×2×3, 2×1×3 and 3×1×2
• We can use multiple instances of boxes. What it means is, we can have two different rotations of a box as part of our maximum height stack.
Solution:
• Generate all 3 rotations of all boxes. The size of rotation array be- comes 3 times the size of original array. For simplicity, we consider depth as always smaller than or equal to width.
• Sort the above generated 3n boxes in decreasing order of base area.
• After sorting the boxes, the problem follows optimal substructure property. Let, property. MSH(i) = Maximum possible Stack Height with box i at top of stack
MSH(i) =
2
(3) • To get overall maximum height, we return Max(MSH(i)) where 0 <
i < 3n
Practice Problems
1. Solve Kleinberg and Tardos, Chapter 6, Exercise 5.
Solution: Let Yi,k denote the substring yiyi+1 . . . yk. Let Opt(k) denote the quality of an optimal segmentation of the substring Y1,k. An optimal segmentation of this substring Y1,k will have quality equalling the quality
3
Max(MSH(j))+hi,wherej
last word (say yi . . . yk ) in the segmentation plus the quality of an optimal solution to the substring Y1,i. Otherwise we could use an optimal solution to Y1,i to improve Opt(k) which would lead to a contradiction.
Opt(k) = max Opt(i) + quality(Yi+1,k) 0
Suppose the first k words are put in the first line, then the number of extra space characters is
i+k−1 s(i,k):=L−k+1− ct
t=i
So we have the recurrence
0ifp≥n−i+1
Trace back the value of k for which Opt(i) is minimized to get the number of words to be printed on each line. We need to compute Opt(i) for n different values of i. At each step p may be asymptotically as big as L. Thus the total running time is O(nL).
3. Solve Kleinberg and Tardos, Chapter 6, Exercise 10.
Solution:
(a) Consider the following example: there are totally 4 minutes, the numbers of steps that can be done respectively on the two machines in the 4 minutes are listed as follows (in time order):
• Machine A: 2, 1, 1, 200 • Machine B: 1, 1, 20, 100
4
Opt(i)= min1≤k≤p{(s(i,k))2+Opt(i+k)}ifp
OPTA(i)=ai +max{OPTA(i−1),OPTB(i−2)}: Similarly, we get the recursive relation for OPTB(i):
OPTB(i)=bi +max{OPTB(i−1),OPTA(i−2)}:
The algorithm initializes OPTA(0) = 0,OPTB(0) = 0,OPTA(1) =
a1 and OPTB(1) = b1. Then the algorithm can be written as follows:
It takes O(1) time to complete the operations in each iteration; there are O(n) iterations; the tracing backs takes O(n) time. Thus, the overall complexity is O(n).
4. Solve Kleinberg and Tardos, Chapter 6, Exercise 24.
Solution: The basic idea is to ask: How should we gerrymander precincts 1 through j, for each j? To make this work, though, we have to keep track of a few extra things, by adding some variables. For brevity, we say that
5
A-votes in a precinct are the voters for part A and B-voter are the votes for part B. We keep track of the following information about a partial solution.
• How many precincts have been assigned to district 1 so far? • How many A-votes are in district 1 so far?
• How many A-votes are in district 2 so far?
So let M[j,p,x,y] = true if it is possible to achieve at least x A-votes in distance 1 and y A-votes in district 2, while allocating p of the first j precincts to district 1. Now suppose precinct j + 1 has z A-votes. To compute M[j+1, p, x, y], you either put precinct j+1 in district 1 (in which case you check the results of sub-problem M[j,p−1,x−z,y]) or in district 2 (in which case you check the results of sub-problem M [j, p, x, y − z]). Now to decide if there’s a solution to the while problem, you scan the entire table at the end, looking for a value of true in any entry from M[n,n/2,x,y] where each of x and y is greater than mn/4. (Since each district gets mn/2 votes total).
We can build this up in the order of increasing j, and each sub-problem takes constant time to compute, using the values of smaller sub-problems. Since there are n2,m2 sub-problems, the running time is O(n2m2).
6