Homework 7 Yuckdonalds

CSCI 3104: Algorithms
Homework 7

1. Yuckdonalds is considering opening a series of restaurants along Quaint Valley Highway
(QVH). The n possible locations are along a straight line, and the distances of these
locations from the start of QVH are, in miles and in increasing order, m1, m2, . . . , mn.
The constraints are as follows:
• At each location, Yuckdonalds may open at most one restaurant. The expected
profit from opening a restaurant at location i is pi
, where pi 0 and i =
1, 2, . . . , n.
• Any two restaurants should be at least k miles apart, where k is a positive integer.
Give an efficient algorithm to compute the maximum expected total profit subject to
the given constraints. What is the running time of your algorithm?
2. A subsequence is palindromic if it is the same whether read left to right or right
to left. For instance, the sequence A, C, G, T, G, T, C, A, A, A, A, T, C, G has many
palindromic subsequences, including A, C, G, C, A and A, A, A, A (on the other hand,
the subsequence A, C, T is not palindromic). Devise an algorithm that takes a sequence
x[1...n] and returns the (length of the) longest palindromic subsequence. Its running
time should be O(n
2
).
3. Cutting cloth. You are given a rectangular piece of cloth with dimensions X × Y ,
where X is width and Y is height (both are positive integers), and a list of n products
that can be made using the cloth. For each product i ∈ [1, n], you know that a rectangle
of cloth of dimensions ai ×bi
is needed and that the final selling price of the product is
ci
. Assume the ai
, bi
, and ci are all positive integers. You have a machine that can cut
any rectangular piece of cloth into two pieces either horizontally or vertically. Write a
python program that determines the best return on the X ×Y piece of cloth, that is, a
strategy for cutting the cloth so that the products made from the resulting pieces give
the maximum sum of selling prices. You are free to make as many copies of a given
product as you wish, or none if desired.
Name your code as LastName FirstName HW7.py. Your code reads two filenames as
the input arguments, the first is input file and the second is output file. A sample
input file is provided at moodle via a separate link. The first line contains the X and
Y values, second line is the n value, and each of the following n lines contains the ai
, bi
,
and ci values for the i-th product i ∈ [1, n]. For the output file, the first line contains
P, T
where P is the maximal profit and T is the total number of cuts, and the following
lines are the individual cuts (one cut per line) in the format:
t, x, y, z, g
where t = 1, 2, . . . is the t-th cut, x and y are the width and height of the current cloth
to cut, z is either 0 (horizontal cut) or 1 (vertical cut), and g is the point of cut. For
example, “10 5 1 2” means to cut a 10 × 5 cloth vertically at 2, resulting in two pieces
of cloth 2 × 5 and 8 × 5.