algorithm - 用一排砖 block 创建 2 根等高的柱子

Question

问题陈述:

有N block 砖(a1，a2，....，aN)。每 block 砖的长度为 L1、L2、....、LN)。使用提供的积木制作 2 个最高的平行柱子(相同长度的柱子)。

约束:

1. 有N block 砖。 5<=N<=50
2. 每 block 砖的长度。 1<=L<=1000
3. 砖 block 长度总和 <= 1000

积木的长度未按尺寸顺序给出。可能有多个长度相同的砖 block 。并非所有的砖 block 都必须用来 build 柱子。

例子:

第一个例子-

N = 5
2, 3, 4, 1, 6

可能的集合:
(2, 6) 和 (3, 4, 1)

答案:8

我的方法:

找到 2 个平行柱子的最大可能长度，即。楼层(N/2)。然后，使用 DP 找到所有可能使用所有砖 block 的总长度。从可能的最高总和 <= floor(N/2) 开始，我采用构成总和的元素的单个子集。然后，再次重复 DP 方法，看看是否可以使用剩余元素形成相同的和。如果可以形成，则输出最大可能的和，否则使用第一个 DP，检查下一个可能形成的最大和，然后再次迭代整个过程。

上述方法的问题在于它只检查元素的一个子集来形成所需的总和。应检查可以形成所需总和的所有可能子集，然后对于这些子集中的每一个，应使用其余元素检查是否可以形成相同的所需总和。问题是在我目前的方法中实现这一点。

第二个例子-

N = 6
3, 2, 6, 4, 7, 1

可能的集合:
(3, 2, 6) 和 (7, 4)

答案:11

在这种情况下，我的代码中可能会出现问题，具体取决于元素(砖 block 长度)作为输入给出的顺序。第一组可能是使用元素 (3, 7, 1) = 11 形成的，但第二组 (2, 6, 4) 不能形成 sum = 11。因此，我的代码开始寻找下一个可能的最大值总和。 10 哪个是错误的。

有人可以建议更好的方法或对我当前方法的可能改进。

Answer 1

我认为您可以使用动态规划来解决这个问题，对于每一对 (x, y)，您可以计算出是否可以使用与目前所考虑的砖 block 不同的砖 block 来构建长度为 x 和 y 的柱子。

依次考虑每 block 砖。一开始只有 (0, 0) 是可能的。当你看到一 block 长度为 L 的砖 block 时，对于每个可能的柱子 (x, y)，都有三个后代 - (x, y)(忽略砖 block )，(x + L, y)(使用第一根柱子上的砖 block ) , 和 (x, y + L)(用第二根柱子上的砖)。

因此，在您考虑了所有积木之后，您将得到一长串可能的对，您只需选择具有相同长度且尽可能长的两个柱子的对。只要永远不会有太多不同的对(您可以从列表中删除任何重复项)，这将是实用的。

假设砖 block 长度是整数，最大柱子长度是 1000，那么只有 1001 * 1001 对可能，所以这应该是实用的，事实上，如果你通过一个大小为 [ 1001, 1001] 并将条目 [x, y] 设置为 1，如果对 (x, y) 是可能的，否则设置为 0。

对于示例的前几个步骤，可达状态是

(0,0) 什么都不考虑

(0,3) (3,0) (0,0) 考虑 3

(0,5) (2,3) (0,3) (5,0) (3,0) (0,2) (2,0) (0,0) 考虑 3 和 2

起初可达状态的数量增长非常快，但由于我们只考虑从 0..1000 开始的值，并且我们只关心数组是否可达，我们可以使用维度为 1001x1001 的 bool 数组来维护它们