求一困扰我五年的高难度算法

Question

有任意N个球放在一个框内，每个球上都标一个小于50的数字，现从框中取球，一次可取多个，只要之和等于54就可以，求：怎样取法，才能使剩下的球最少，并打印出结果。（欢迎大家踊跃发表自己的想法）

Answer 1

N个球，如果N>=50的话，肯定有重复的数字。

Answer 2

将N个球排序，比如从小到大，然后从前面开始取小的数，累加＝54，则剩余的球最少。>54的时候，从已经取得的球中由大到小往回算，直到＝54

Answer 3

同意9楼的方法，
但是注意点就是“>54的时候，从已经取得的球中由大到小往回算，直到＝54”，有可能不=54，就直接< 54了。可能又需要从小往大加，这时也可能因球数字关系，始终得不到=54。

Answer 4

先从小到大排列
设sum :=0,依次累加，while sum>=54时跳出，并累加次数k；
if sum=54 then 即得到结果
else   //大于54
  temp := a[1]+..a[k-2];
  sum := temp +a[k];           //就只能试a[1]+..a[k-2]的和再加a[k]
  if sum=54 then 即得到结果
  elseif sum>54 then 
     temp := a[1]+..a[k-3];
     sum := temp +a[k]; 
     if //循环大于、小于、等于的情况
  else sum<54 的情况
总之，貌似有点乱了 

Answer 5

问题分析 首先 框中的球是N个  每个球都是 0到 50 球取出N个球的和是54 并且剩下的球最少
解决：
一 首先必须要给N个球一个顺序 这是个排序问题
二 解决一个顺序数组 前多少个数之和是54 （分>,< ,= 三种情况）

Answer 6

1.这是一个最优问题，如果不出意外，应该是一个NP完全问题。
2.此类题目的解法，可以应用整数规划，相关知识不是那么容易弄懂的。
3.最简单的方法，就是穷举，把所有可能和为54的球的可能性穷举，找一种球个数最多的，剩下就是最少的。
4.此问题如果有好的解法，可以推广到其他优化问题中，感觉这个问题可以和图的最大独立集建立关系。
5.这个问题思考了5年了，很佩服。不过如果这个问题能够很好的解决，估计P=NP可能也有思路了。结论：该放弃还是放弃。
:-)

Answer 7

想法很好,可惜这个数字太大了,几乎没法穷举 
比方说使用了1..50 U 1..40 U 1..30 U 1..20 U 1..10这样的一个集合,其和为54的不同组合超过了18.7w，就算全部列出了，要对其中的某一个组合进行判定也是很恐怖的一个事情。

Answer 8

kan看大家的回复也长见识啊。