求助：给出一组整数，例如，（19,27,42，...）现在请把他们分成三堆，使得每一堆的和相等

给出一组整数，例如，（19,27,42，...）现在请把他们分成三堆，使得每一堆的和相等；  
a。如何判断该问题是否有解  
b。请给出解决方案的算法（尽可能每堆相等的算法）昨天笔试的时候遇到的，谢谢啦！

解决方案 »

  1.   

    似乎不那么容易呐。分成三堆，每堆和相等，说明每堆的和就只能是 所有数总和的1/3。但这样只能判断出如果总和如果不是3的倍数就一定无解，但是否一定有解还没法直接判断出来。接下来这个问题就变成著名的“背包”问题了：
    已知各物品重量，有三个背包，承重能力刚好是所有物品重量的1/3，请问所有物品应如何装入背包中。笔试的话，似乎很够喝一壶的了。
      

  2.   

    判断该问题是否有解，用搜索足矣（如果根数过多可能会爆空间，爆时间）。至于，尽可能接近的算法。感觉不是很容易。搜索只能给出如果有解，解的情况。
      

  3.   


    搜索？？是指穷举吗？那样太暴力了吧？！
      

  4.   

    先考虑是否能被3整除，如果不行那肯定不能分。
    如果可以，那么可以先排序，按从大到小，如果最大的大于了总和的1/3那么也肯定不行。
    在排除以上两种情况下，然后开始循环搜索吧。
      

  5.   

    尽可能没堆都相等的话比较难