首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

垒砖有关问题(转自Topcoder)

2012-02-09 
垒砖问题(转自Topcoder)问题:现有高度各不同的一堆砖,现要求将其垒成两个高度相同的台子输入:int [] brick

垒砖问题(转自Topcoder)
问题:现有高度各不同的一堆砖,现要求将其垒成两个高度相同的台子

输入:int [] bricks(各砖高度)
输出:int(有方案则输出台子高度,没有则为-1)
例如:
{ 2, 3, 5 }
Returns: 5
{ 10, 9, 2 }
Returns: -1

下面是我找到的一位牛人的算法,但是看不懂

Java code
public class EqualTowers {    /**     * @param args the command line arguments     */    private static final int MAX=250000;    private int[][] mem= new int[50][MAX+1];    private int[] bricks;    public  int height(int[] bricks){        this.bricks=bricks;        return go(0,0);    }    public int go(int k,int t){        if(t>MAX){            return -1;        }        if(k==bricks.length)        {            return ((t==0)?0:-1);        }        if(mem[k][t]==0){            //add to the First tower            int d1=go(k+1,t+bricks[k]);            //do nothing;            int d2=go(k+1,t);            //add to the second tower            int d3=go(k+1,Math.abs(bricks[k]-t));            if(d3!=-1){                d3+=Math.min(t,bricks[k]);            }            //pick the best result            mem[k][t]=Math.max(d1,Math.max(d2, d3));            //Prevent a 0-size tower in the final result;            if(t==0&&k==0&&mem[k][t]==0){                mem[k][t]=-1;            }            mem[k][t]+=2;        }        return mem[k][t]-2;    }    public static void main(String[] args) {        // TODO code application logic here    }}

欢迎讨论!

[解决办法]
先把所有砖块的高度总和/2=s2.

然后循环求砖块高度数组中的无序组合
如从2,3,5中选两个,结果有:2 ,3 2 ,5 3, 5 三种组合
在把求的组合之和于s2比较相等则输出;
C# code
 
using System; 
using System.Collections.Generic; 
using System.Text; 

namespace ConsoleApplication1 

  class Program 
  { 
    static void Main(string[] args) 
    { 
      int[] array ={ 2,3,5,8,9,7,0,34,29,11};
     
      int n=4; 
      Method(array,n); 
    } 
    public static void Method(int[] arr, int N) 
    { 
        int[] prt = new int[100];
        int s2=0;
     
        for (int i = 0; i < prt.Length; i++) 
        { 
          prt[i] = -9999; 
        } 
        for(int i=0;i <arr.Length;i++)
        {
        s2+=arr[i];
        }
        s2/=2;

        bool flog=fasle;
        for (int i = 0; i < arr.Length; i++) 
        { 
         
          int prti = 0; 
          int k; 
          for (k = i; k < N + i - 1; k++, prti++) 
          { 
            prt[prti] = arr[k]; 
          } 
          for (int j = k; j < arr.Length; j++) 
          { 
            prt[prti] = arr[j];
            int s2test=0; 
            foreach (int u in prt) 


            { 
              if (u == -9999) break; 
              s2test+=prt[u]; 
            }
            if(s2==s2test)
            { 
            Console.Write("{0}\t", s2test);
            flog=true; break; 
            }
          } 
          if (i + N == arr.Length) break; 
          if(flog==fasle) Console.Write("-1");

        } 
      Console.ReadLine(); 
    } 
  } 



[解决办法]
假如bricks中放着,a,b,c,d 5个数.
我设一HashMap <Integer,Integer> (这个java中的类)

依次对bricks中的每一个数做以下运算:
如果HashMap中包含bricks[i],则算法结束。否则把bricks[i]与HashMap中的各个数相加,并看看结果是否包含在HashMap中,如果是算法结束,否则把放入HashMap.再把brichs[i]放入HashMap.

第一次:HashMap:a.
第二次:HashMap: a,b+a,b
第三次:HashMap: a,b+a,b,c+a,c+b+a,c+b,c
第四次:HashMap: a,b+a,b,c+a,c+b+a,c+b,c,d+a,d+b+a,d+b,d+c+a,d+c+b+a,d+c+b,d+c,d


[解决办法]
楼主找到的程序,我给加了注释,希望大家都能看得懂。
Java code
public class EqualTowers {    /**     * @param args the command line arguments     */    private static final int MAX=250000;    private int[][] mem= new int[50][MAX+1];    private int[] bricks;    public  int height(int[] bricks){        this.bricks=bricks;        return go(0,0);    }    /**     *      * @param k 垒第k+1块砖(数组下标从0开始)。     * @param t 两座塔的高度差的绝对值。     * @return 有解时,返回较矮塔高度的最大值。在塔顶,两塔高度差为零,此时的返回值即为最终结果。     *         无解时,返回-1。     */    public int go(int k,int t){        // 高度差的值超出了此程序设计的缓存能力。        if(t>MAX){            return -1;        }        // 所有砖块垒好后,根据高度差的值判断是否有解。        if(k==bricks.length)        {            return ((t==0)?0:-1);        }        // 如果mem[k][t]==0,意味着go[k][t]是第一次被调用。        // 否则直接从mem[k][t]中读取第一次调用的计算结果。        // 这是为了提高递归算法效率而采取的一种常用技巧。        if(mem[k][t]==0){            // 将第k+1块砖垒到较高的塔上,由于之前两塔高度差为t,因此此次操作后高度差变成t+bricks[k]。            // 此操作对于较矮的塔的高度没有影响。            int d1=go(k+1,t+bricks[k]);            // 舍弃第k+1块砖,高度差没有变化。            // 此操作对于较矮的塔的高度没有影响。            int d2=go(k+1,t);            // 将第k+1块砖垒到较矮的塔上,高度差变成abs(bricks[k]-t)。            int d3=go(k+1,Math.abs(bricks[k]-t));            if(d3!=-1){                // 如果方案可行,从最后一块砖开始垒,同时计算当前较矮的塔的高度。                // 放置第k+1块砖之前,两塔高度分别为d3, d3+t;                // 放置第k+1块砖之后,两塔高度分别为d3+bricks[k],d3+t;                // 此时,较矮的塔高度为d3+min(t,bricks[k])。                d3+=Math.min(t,bricks[k]);            }            // 选取最佳结果            mem[k][t]=Math.max(d1,Math.max(d2, d3));            // 所有砖块都被舍弃的情况,无解。            if(t==0&&k==0&&mem[k][t]==0){                mem[k][t]=-1;            }            // 将计算的结果保存到mem数组中,考虑到            //    mem[k][t]==d1==d2==d3==0            //    mem[k][t]==d1==d2==d3==-1            // 两种情况,为了保证下次调用时m[k][t]不为0,所以在现有值的基础上加2。            mem[k][t]+=2;        }        return mem[k][t]-2;    }    public static void main(String[] args) {        // TODO code application logic here    }}
[解决办法]
还是背包问题,就是一个sum/2的背包,LZ给出的牛人的方法似乎是用状态压缩的动态规划解的,
应该是个不错的办法,不过不知道原题是否有些额外的条件,程序中定义的数组似乎有点小。

另外可以看看这个帖子,最近这个问题讨论了好多次了。从C版到C#版,还有算法版,题目都是找Sum/2大小的背包。
只不过这道题是要找刚好装满Sum/2的背包,剩下几道是找最接近Sum/2的,相比,这道题还要简单一些。


http://topic.csdn.net/u/20090511/23/a482be66-6598-46fa-be19-e7e356e2244b.html
[解决办法]

探讨
还是背包问题,就是一个sum/2的背包,LZ给出的牛人的方法似乎是用状态压缩的动态规划解的,
应该是个不错的办法,不过不知道原题是否有些额外的条件,程序中定义的数组似乎有点小。

另外可以看看这个帖子,最近这个问题讨论了好多次了。从C版到C#版,还有算法版,题目都是找Sum/2大小的背包。
只不过这道题是要找刚好装满Sum/2的背包,剩下几道是找最接近Sum/2的,相比,这道题还要简单一些。
http://topic.csdn.net/u…

热点排行