用一排砖块创建 2 根等高的柱子

Question

问题陈述：

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

限制条件：

有N块砖。 5<=N<=50
每块砖的长度。 1<=大号<=1000
积木长度总和 <= 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。因此，我的代码开始寻找下一个可能的最大值总和。 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] 设置为 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 的布尔数组来维护它们

Answer 2

最近我在准备三星能力测试时试图解决这个问题。我构建了解决方案，这可能会帮助你们练习。多亏了https://whosebug.com/users/240457/mcdowella，我才能够使用他的策略解决这个问题。

public class Pillars {
    public static int h=0,mh=0; 
    public static void main(String[] args)  {   
        java.util.Scanner scan = new java.util.Scanner (System.in);
        int n = scan.nextInt();
        int a[]=new int[n];     
        for(int i=0;i<n;i++)
        {
            a[i]=scan.nextInt();
            mh+=a[i];
        }
        mh/=2;// the height of the two pillars is the total, then single pillar can't be more than half of total 
        maxHeight(0,0,a,0);
        // if no pillars can be built using the data, this print statement is executed
        System.out.println("Maximum Height Formed with the given Data "+h);     
    }

    public static void maxHeight(int x,int y,int a[],int i)
    {
        if(x==y && x!=0 && x>h)// whether the heights formed are equal or not 
        {
            h=x;
            if(h==mh) // if equal then print and exit the program
            {
                System.out.println("Maximum Height Formed with the given Data "+h);
                System.exit(0);
            }
        }
        if(i<a.length )
        {
            maxHeight(x+a[i],y,a,i+1);
            maxHeight(x,y+a[i],a,i+1);          
        }       
    }
}

Answer 3

嗯，这道题用递归就可以解决了。但对于较大的 n 值，它不会有效。这是我的代码

#include <iostream>
using namespace std;

void solve(int a[], int vis[], int p1, int p2, int n, int &ans){
    if(p1 == p2){

        if(p1 > ans){
            ans = p1;
        }
    }

    for(int i=0 ; i<n ; ++i){

        if(vis[i] == 0){
            vis[i] = 1;
            solve(a, vis, p1 + a[i], p2, n, ans);
            solve(a, vis, p1, p2 + a[i], n, ans);
            vis[i] = 0;
        }
    }
}
int main(){

    int n;
    cin>>n;
    int a[n];

    for(int i=0 ; i<n ; ++i){
        cin>>a[i];
    }

    int vis[n] = {0};
    int ans = -1;
    solve(a,vis,0,0,n,ans);

    cout<<ans;
    return 0;
}

用一排砖块创建 2 根等高的柱子

Create 2 pillars of equal height from an array of bricks

algorithm

tree

graph

dynamic-programming

backtracking