1
1.
2.
3.
CSCI 570 – Fall 2020 – HW6
Due October 14th 11:59 p.m.
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.
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”.
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.
For example, here are 3 balloons [6, 5, 9]. After bursting the middle one, you will get 6 ∗ 5 ∗ 9 = 270 coins. The balloons array will become [6, 9],
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 maximum coins you can collect by bursting the balloons wisely. Analyze the running time of your algorithm.
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
1
4.
2
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.
Practice Problems
1. Solve Kleinberg and Tardos, Chapter 6, Exercise 5. 2. Solve Kleinberg and Tardos, Chapter 6, Exercise 6. 3. Solve Kleinberg and Tardos, Chapter 6, Exercise 10. 4. Solve Kleinberg and Tardos, Chapter 6, Exercise 24.
2