从砖块阵列创建2个等高的柱子

Question

问题声明：

有N块砖（a1，a2，...，aN）。每块砖的长度为L1，L2，...，LN）。使用提供的砖块制作2个最高平行支柱（相同长度的支柱）。

约束：

1. 有N个砖块。 5 < = N < = 50
2. 每块砖的长度。 1 < = L < = 1000
3. 砖块的长度之和= < 1000砖块

长度不是在大小顺序给出。可能有多块砖可能具有相同的长度。不是所有的砖都必须用来创建支柱。

实施例：

第一例 -

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

可能集合：
（2,6）和（3,4 1）

答：8

我的方法：

寻找2个平行支柱的最大可能长度，即。地板（N/2）。然后，使用DP来查找所有可能使用所有砖块的总和长度。从尽可能高的总数开始< = floor（N/2），我拿出构成总和的元素的一个子集。然后，再次重复DP方法来查找是否可以使用其余元素形成相同的和。如果可以形成，那么输出是可能的最高总和，否则使用第一个DP，检查可能形成的下一个最高可能总和，然后再次重复整个过程。

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

第二例 -

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

可能集合：
（3，2,6）和（7,4）

答案：11

在我的代码的问题可能依赖于在其中的元件（砖的长度）被给定为输入的顺序来在这种情况下。有可能第一组是使用元素（3,7,1）= 11形成的，但第二组（2，6，4）不能形成sum = 11。因此，我的代码开始寻找下一个可能的最大值总和.ie。 10这是错误的。

有人可以提出更好的方法或可能改进我目前的做法。

Answer 1

我认为你可以用动态规划解决这个问题，对于每对（x，y），你可以使用迄今为止考虑的砖块中的不同砖块建立长度为x和y的支柱。

考虑每块砖。在开始时只有（0，0）是可能的。当你看到一块长度为L的砖，那么对于每个可能的支柱（x，y），有三个后代 - （x，y）（忽略砖），（x + L，y）（使用第一支柱上的砖） ，和（x，y + L）（使用第二个支柱上的砖）。

所以在你考虑了所有的砖头之后，你会有一长串可能的对子，你只需选择一对长度相同且长度尽可能长的柱子。只要没有太多不同的对（这可以从列表中删除任何重复项），这将是实用的。

假设砖的长度是整数，最大支柱长度是1000，那么只有1001 * 1001个可能的成对，所以这应该是实用的，事实上，如果通过具有大小的数组来存储成对[1001,1001]并且如果对（x，y）是可能的，则将条目[x，y]设置为1，否则设置0。

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

（0,0）考虑什么

（0,3）（3,0）（0,0）考虑3

考虑3和2的

（0,5）（2,3）（0,3）（5,0）（0,0）

可达状态的数量起初增长非常快，但由于我们只考虑0..1000的值，我们只关心数组是否可达，我们可以使用ab来维护它们维数的排列数组1001x1001