问题陈述:
有 N 个砖块 (a1, a2, ...., aN)。每块砖的长度为 L1, L2, ...., LN)。使用提供的砖块制作 2 个最高的平行柱子(相同长度的柱子)。
约束:
砖块的长度没有按尺寸顺序给出。可能有多个具有相同长度的砖块。并非所有的砖块都必须用来制作柱子。
例子:
第一个例子-
N = 5
2, 3, 4, 1, 6
可能的集合:
(2, 6) 和 (3, 4, 1)
答案:8
我的方法:
找到 2 个平行支柱的最大可能长度，即。地板(N/2)。然后，使用 DP 找到所有可能使用所有砖块的总和长度。从可能的最高总和
上述方法的问题在于它只检查元素的一个子集以形成所需的总和。应该检查可以形成所需总和的所有可能子集，然后对于这些子集中的每一个，使用剩余元素检查是否可以形成相同的所需总和。问题是在我目前的方法中实现了这一点。
第二个例子-
N = 6
3, 2, 6, 4, 7, 1
可能的集合:
(3, 2, 6) 和 (7, 4)
答案:11
在这种情况下，我的代码中可能会出现问题，具体取决于元素(砖长度)作为输入的顺序。第一个集合可能是使用元素 (3, 7, 1) = 11 形成的，但第二个集合 (2, 6, 4) 不能形成 sum = 11。因此，我的代码开始寻找下一个可能的最大值总和。即。 10 这是错误的。
有人可以在我目前的方法中提出更好的方法或可能的改进。
最佳答案
我认为您可以通过动态编程来解决这个问题，其中对于每一对 (x, y)，您可以计算出是否可以使用与目前考虑的砖块不同的砖块来 build 长度为 x 和 y 的柱子。
依次考虑每块砖。一开始只有 (0, 0) 是可能的。当你看到一块长度为 L 的砖时，对于每个可能的柱子 (x, y) 都有三个后代 - (x, y)(忽略砖块)，(x + L, y)(使用第一根柱子上的砖块) , 和 (x, y + L)(使用第二根柱子上的砖块)。
所以在你考虑了所有的积木之后，你会得到一长串可能的配对，你只需选择具有相同长度和尽可能长的两根柱子的配对。只要没有太多不同的对(您可以从列表中删除任何重复项)，这将是实用的。
假设砖的长度是整数，最大柱长是 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 数组来维护它们
关于algorithm - 从一组砖块中创建 2 个等高的柱子，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43484942/