java递归: best collection of numbers

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

这个问题似乎偏离主题，因为它缺乏足够的信息来诊断问题。 更详细地描述您的问题或 include a minimal example在问题本身。

已关闭 9 年前。

Improve this question

给定一个整数数组并给定另一个整数。如何使用递归从该数组中查找整数集合，以便该集合的总和最接近给定的整数？例如，给定 array:1,2,3 且给定整数为 5，则该方法返回 2,3；另一个例子:如果给定的数组是:35,14,45,3，给定的整数是50，那么该方法返回35和14。

Answer 1

它看起来像一个家庭作业，所以我不会放置任何代码，但尝试解释算法。想象一下，您得到了 [35, 14, 45, 3] 和 50；

  1. First sort the array in descending order: [45, 35, 14, 3] 
  2. You should remove the 1st item in the array and take it or leave it
  3. So you'll have two smaller problems: 
      [35, 14, 3] and 5  (45 is taken)
      [35, 14, 3] and 50 (45 is left)
  4. To cut story short keep the best score so far: 5 in your case. 
     It let you trim some negative value branches
      [35, 14, 3] and 5  (45 is taken) is the best so far 
  5. If the array is not empty, go to the step 2

整个轨迹是

  [35, 14, 3] and   5 (45 taken) // the best score so far
      [14, 3] and -30 (45, 35 taken) // trim: worse than the best score so far
      [14, 3] and   5 (45 taken)
          [3] and  -9 (45, 14 taken) // trim
          [3] and   5 (45 taken)
           [] and   2 (45, 3 taken) // the best score so far
           [] and   5 (45 taken)    
  [35, 14, 3] and  50 (nothing taken)
      [14, 3] and  15 (35 taken)
          [3] and   1 (35, 14 taken) // the best score so far
           [] and  -2 (35, 14, 3 taken) 
          [3] and  15 (35 taken) 
           [] and  12 (35, 3 taken) 

       ...           

最后，迄今为止最好的分数 1 是采用 (35, 14) 的解决方案。实现时，您只需进行两次递归调用:一次用于“take”，一次用于“leave”。