动态规划问题 [英] Dynamic programming question

问题描述

一个马戏团正在设计一种常规塔组成的人站在顶上彼此的 肩膀上。为了实际和美观的原因，每个人必须既比低于他或她的人更短，更轻。由于高度和每个人在马戏团的权重，写一个方法来计算的人尽可能多 在这样的塔。

A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.

示例：
输入（HT，重量）（65，100）（70，150）（56，90）（75，190）（60，95）（68，110）
输出：最长塔是长度为6，并包括从上到下：（56，90）（60,95）（65100）（68110）（70150）（75190）

EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

有人建议我下面： 这是可以做到如下：

Someone suggested me the following: It can be done as follows:

1. 排序输入从大到小依次重量，发现HIGHT的最长下降序列。
2. 排序输入从大到小依次HIGHT和发现权重的最长下降序列。

1和2.取最大值

我不明白为什么我们需要做两个步骤1和2斜面，我们只是做1和找到答案。如果没有，请举个例子，其中仅从事第1步没有给出答案？

I dont understand why we need to do both steps 1 and 2. Cant we just do 1 and find the answer. IF not , please give example in which doing only step 1 does not give answer?

推荐答案

1和2的结果必须是相同的。这是不可能的其中之一是短的，因为在溶液中的元素降二者中的身高和体重，所以如果它满足1或2，将满足其它，以及，如果这将是短它不会是最长的。

Result of 1 and 2 has to be same. It's not possible that one of them is shorter, because in a solution elements are descending both in height and weight so if it satisfies 1 or 2 it will satisfy the other as well, If it would be shorter it wouldn't be the longest.

这篇关于动态规划问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！