时间戳

首页 > 解决方案 > 算法 - 如何找到最高的人塔的高度

algorithm - 算法 - 如何找到最高的人塔的高度

问题描述

这是问题描述：

The Amazing Circus 有 K 杂技演员，他们通过在彼此的肩膀上跳跃来表演伟大的人类塔。马戏团总监希望建造最高的塔，以进入吉尼斯纪录并吸引更多顾客。

每个杂技演员i都有体重W[i]和力量S[i]。一个杂技演员可以背着一堆杂技演员，其总重量在 S[i] 以内。这应该包括 W[i]，它自己的权重，所以假设 S[i]≥W[i] 总是。

返回惊人马戏团可以建造的最高人类塔的高度。

约束：

3 <= K <= 5000

1 <= 重量 <= 容量 <= 10^6。

所以对于这个问题，一开始我觉得这个问题和其他的贪心算法问题有些相似。但是当我查看约束时，似乎约束相对较大，因此蛮力或穷举搜索效果不佳。关于如何解决这个问题的任何想法？

标签： algorithm

解决方案

这是一个带有O(n^2)搜索空间的解决方案（n = K，杂技演员的总数）。让我们f(i, h)表示最轻的塔的重量h，直到i杂技演员，杂技演员按strength升序排列。然后：

f(i, h) = min(
  f(i - 1, h),
  weight(i) + f(i - 1, h - 1)
     if strength(i) ≥ weight(i) + f(i - 1, h - 1) else Infinity
)

解释排序技巧，改编自COMP3121/9101/3821/9801 Lecture Notes；更多关于动态规划（DP）；LiC：阿列克斯·伊格尼亚托维奇；计算机科学与工程学院；新南威尔士大学；澳大利亚悉尼：

我们想证明我们可以重新排列任何合法的塔以通过strength上升来排序。为此，我们需要证明任何连续的对

(1) strength(a_i+1) < strength(a_i)

可以合法地交换，从那时起我们可以应用冒泡排序。换句话说，那

(2) (Sum j=1...i-1 of weight(a_j)) + weight(a_i+1) + weight(a_i) ≤ strength(a_i)

原来的，合法的塔有

(3) (Sum j=1...i−1 of weight(a_j)) + weight(a_i) + weight(a_i+1) ≤ strength(a_i+1)

将 (1) 代入右侧并在左侧交换最后两项：

(Sum j=1...i−1 of weight(a_j)) + weight(a_i+1) + weight(a_i) ≤ strength(a_i)

推荐阅读