91影视

Cutting cloth. You are given a rectangular piece of cloth with dimensions $\mathit{X}\mathbf{脳}\mathit{Y}$, where$\mathit{X}$ and $\mathit{Y}$are positive integers, and a list of products that can be made using the cloth. For each product$\mathit{i}\mathbf{}\mathbf{鈭�}\mathbf{}\left[1,n\right]$ you know that a rectangle of cloth of dimensions${\mathbf{a}}_{\mathbf{i}}\mathbf{脳}\mathbf{}{\mathbf{b}}_{\mathbf{i}}$ is needed and that the final selling price of the product is ${\mathit{c}}_{\mathbf{i}}$. Assume the,${\mathit{a}}_{\mathbf{i}}$ ${\mathit{b}}_{\mathbf{i}}$and${\mathit{c}}_{\mathbf{i}}$ are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design an algorithm that determines the best return on the$\mathit{X}\mathbf{脳}\mathit{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.

Consider the following variation on the change-making problem (Exercise 6.17): you are given denominations ${\mathit{x}}_{\mathbf{1}}\mathbf{,}\mathbf{\text{鈥�}}{\mathit{x}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{..}\mathbf{,}{\mathit{x}}_{\mathbf{n}}$, and you want to make change for a value $\mathbf{v}$, but you are allowed to use each denomination at most once. For instance, if the denominations are $\mathbf{1}\mathbf{,}\mathbf{}\mathbf{5}\mathbf{,}\mathbf{}\mathbf{10}\mathbf{,}\mathbf{}\mathbf{20}\mathbf{,}$then you can make change for $\mathbf{16}\mathbf{}\mathbf{=}\mathbf{}\mathbf{1}\mathbf{}\mathbf{+}\mathbf{}\mathbf{15}$and for $\mathbf{31}\mathbf{}\mathbf{=}\mathbf{}\mathbf{1}\mathbf{}\mathbf{+}\mathbf{}\mathbf{10}\mathbf{}\mathbf{+}\mathbf{}\mathbf{20}$but not for 40(because you can鈥檛 use 20 twice).

Input: Positive integers; ${\mathbf{x}}_{\mathbf{1}}\mathbf{,}\mathbf{\text{鈥�}}{\mathbf{x}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{..}\mathbf{,}{\mathbf{x}}_{\mathbf{n}}$another integer $\mathbf{v}$.

Output: Can you make change for $\mathbf{v}$, using each denomination${\mathbf{x}}_{\mathbf{i}}$ at most once?Show how to solve this problem in time $\mathbf{O}\left(\mathrm{nV}\right)$.

A contiguous subsequence of a list $\mathbf{S}$is a subsequence made up of consecutive elements of $\mathbf{S}$. For instance, if $\mathbf{S}$is $\mathbf{5}\mathbf{,}\mathbf{}\mathbf{15}\mathbf{,}\mathbf{}\mathbf{鈭�}\mathbf{30}\mathbf{,}\mathbf{}\mathbf{10}\mathbf{,}\mathbf{}\mathbf{鈭�}\mathbf{5}\mathbf{,}\mathbf{}\mathbf{40}\mathbf{,}\mathbf{}\mathbf{10}$

Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero).For the preceding example, the answer would be $\mathbf{10}\mathbf{,}\mathbf{}\mathbf{鈭�}\mathbf{5}\mathbf{,}\mathbf{}\mathbf{40}\mathbf{,}\mathbf{}\mathbf{10}$, with a sum of 55. (Hint: For each $\mathit{j}\mathbf{鈭�}\left\{1,2,...,n\right\}$, consider contiguous subsequences ending exactly at position j.)

Optimal binary search trees. Suppose we know the frequency with which keywords occur in programs of a certain language, for instance:

$\begin{array}{l}\mathbf{begin}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{5}\mathbf{\%}\\ \mathbf{do}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{40}\mathbf{\%}\\ \mathbf{else}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{8}\mathbf{\%}\\ \mathbf{end}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{4}\mathbf{\%}\end{array}$

$\begin{array}{l}\mathbf{if}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{10}\mathbf{\%}\\ \mathbf{then}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{10}\mathbf{\%}\\ \mathbf{while}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{23}\mathbf{\%}\end{array}$

We want to organize them in a binary search tree, so that the keyword in the root is alphabetically bigger than all the keywords in the left subtree and smaller than all the keywords in the right subtree (and this holds for all nodes). Figure 6.12 has a nicely-balanced example on the left. In this case, when a keyword is being looked up, the number of comparisons needed is at most three: for instance, in finding 鈥渨hile鈥�, only the three nodes 鈥渆nd鈥�, 鈥渢hen鈥�, and 鈥渨hile鈥� get examined. But since we know the frequency 196 Algorithms with which keywords are accessed, we can use an even more fine-tuned cost function, the average number of comparisons to look up a word. For the search tree on the left, it is

$\mathbf{cost}\mathbf{=}\mathbf{1}\left(0.04\right)\mathbf{+}\mathbf{2}\left(0.40+0.10\right)\mathbf{+}\mathbf{3}\left(0.05+0.08+0.10+0.23\right)\mathbf{=}\mathbf{2}\mathbf{.}\mathbf{42}$

By this measure, the best search tree is the one on the right, which has a cost of Give an efficient algorithm for the following task. Input: n words (in sorted order); frequencies of these words: ${\mathit{p}}_{\mathbf{1}}\mathbf{,}{\mathit{p}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{p}}_{\mathbf{n}}\mathbf{.}$

Output: The binary search tree of lowest cost (defined above as the expected number of comparisons in looking up a word).

Figure 6.12 Two binary search trees for the keywords of a programming language.

Give an O(nt) algorithm for the following task. Input: A list of n positive integers $\mathbf{a}\mathbf{1}\mathbf{,}\mathbf{a}\mathbf{2}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathbf{an}$; a positive integer $\mathbf{}\mathit{t}$. Question: Does some subset of the a_i鈥檚 add up to t? (You can use each a_i at most once.) (Hint: Look at subproblems of the form 鈥渄oes a subset of$\left\{a_1,a_2,...,a_i\right\}$ add up to ?鈥�)

You are going on a long trip. You start on the road at mile post $0$. Along the way there are$n$ hotels, at mile posts $a_1<a_2<...<a_n$ , where each$a_i$ is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance $a_n$), which is your destination. You鈥檇 ideally like to travel miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is ${\left(200鈭�x\right)}^{\mathbf{2}}$. You want to plan your trip so as to minimize the total penalty- that is, the sum, over all travel days, of the daily penalties.Give an efficient algorithm that determines the optimal sequence of hotels at which to stop

Given two strings $\mathit{x}\mathbf{=}{\mathit{x}}_{\mathbf{1}}{\mathit{x}}_{\mathbf{2}}\mathbf{路}\mathbf{路}\mathbf{路}{\mathit{x}}_{\mathbf{n}}$and $\mathit{y}\mathbf{=}{\mathit{y}}_{\mathbf{1}}{\mathit{y}}_{\mathbf{2}}\mathbf{路}\mathbf{路}\mathbf{路}{\mathit{y}}_{\mathbf{m}}$, we wish to find the length of their longest common subsequence, that is, the largest k for which there are indices ${\mathit{i}}_{\mathbf{1}}\mathbf{<}{\mathit{i}}_{\mathbf{2}}\mathbf{<}\mathbf{路}\mathbf{路}\mathbf{路}\mathbf{<}{\mathit{i}}_{\mathbf{k}}$and ${\mathit{j}}_{\mathbf{1}}\mathbf{<}{\mathit{j}}_{\mathbf{2}}\mathbf{<}\mathbf{路}\mathbf{路}\mathbf{路}\mathbf{<}{\mathit{j}}_{\mathbf{k}}$with ${\mathit{x}}_{\mathbf{i}\mathbf{1}}{\mathit{x}}_{\mathbf{i}\mathbf{2}}\mathbf{路}\mathbf{路}\mathbf{路}{\mathit{x}}_{\mathbf{i}\mathbf{k}}\mathbf{=}{\mathit{y}}_{\mathbf{j}\mathbf{1}}{\mathit{y}}_{\mathbf{j}\mathbf{2}}\mathbf{路}\mathbf{路}\mathbf{路}{\mathit{y}}_{\mathbf{j}\mathbf{k}}$. Show how to do this in time $\mathbf{0}\left(mn\right)$.

Suppose two teams, A and B, are playing a match to see who is the first to win games (for some particular n). We can suppose that A and B are equally competent, so each has a 50% chance of winning any particular game. Suppose they have already played i+j games, of which A has won i and B has won j. Give an efficient algorithm to compute the probability that A will go on to win the match. For example, if i=n-1 and j=n-3 then the probability that A will win the match is $\frac{\mathbf{7}}{\mathbf{8}}$, since it must win any of the next three games.

The garage sale problem (courtesy of Professor Lofti Zadeh). On a given Sunday morning, there are n garage sales going on, ${\mathbf{g}}_{\mathbf{1}}\mathbf{,}{\mathbf{g}}_{\mathbf{2}}\mathbf{,}{\mathbf{g}}_{\mathbf{3}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathbf{g}}_{\mathbf{n}}$. For each garage sale ${\mathbf{g}}_{\mathbf{j}}$, you have an estimate of its value to you, ${\mathbf{v}}_{\mathbf{j}}$. For any two garage sales you have an estimate of the transportation cost ${\mathbf{d}}_{\mathbf{ij}}$of getting from ${\mathbf{g}}_{\mathbf{i}}$to ${\mathbf{g}}_{\mathbf{j}}$. You are also given the costs ${\mathbf{d}}_{\mathbf{0}\mathbf{j}}$and ${\mathbf{d}}_{\mathbf{j}\mathbf{0}}$of going between your home and each garage sale. You want to find a tour of a subset of the given garage sales, starting and ending at home, that maximizes your total benefit minus your total transportation costs. Give an algorithm that solves this problem in time $\mathbf{O}\mathbf{}\left(n^2{2}^n\right)$.

(Hint: This is closely related to the traveling salesman problem.)

Exon chaining.Each gene corresponds to a subregion of the overall genome (the DNA sequence); however, part of this region might be 鈥渏unk DNA.鈥� Frequently, a gene consists of several pieces called exons, which are separated by junk fragments called introns. This complicates the process of identifying genes in a newly sequenced genome.

Suppose we have a new DNA sequence and we want to check whether a certain gene (a string) is present in it. Because we cannot hope that the gene will be a contiguous subsequence, we look for partial matches鈥攆ragments of the DNA that are also present in the gene (actually, even these partial matches will be approximate, not perfect). We then attempt to assemble these fragments.

Let x $\left[1Kn\right]$denote the DNA sequence. Each partial match can be represented by a triple $\left(l_i,r_i,w_i\right)$, where $x\left[l_{i}K{r}_i\right]$is the fragment and is a weight

representing the strength of the match (it might be a local alignment score or some other statistical quantity). Many of these potential matches could be false, so the goal is to find a subset of the triples that are consistent (nonoverlapping) and have a maximum total weight.

Show how to do this efficiently.