子集和递归获得尽可能接近到一个给定数目

本文介绍了子集和递归获得尽可能接近到一个给定数目的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

可能重复：   子集和算法

我有一个非常简单的问题，我想不通。我给数字数组和值我需要得到尽可能接近要通过使套组合。这种算法是递归。结果不能超过给定数。

I have a very easy problem which I can't figure out. I'm given an array of numbers and a value I need to get as close as possible to by making combinations of the sets. This algorithm has to be recursively. The result can't exceed the given number.

例如，给定的阵列{6,9，4,2，7}和我需要得到尽可能接近到14。然后，结果是13（通过选择元件9和4）。

For example, given an array of {6, 9, 4, 2, 7} and I need to get as close as possible to 14. Then the result is 13 (by choosing the elements 9 and 4).

这是我到目前为止有：

有两个参数的递归函数：一个索引，提供有关你即将加入（或不）的单元信息和之和为止。对于每一个元件I做出二元决策：它添加到sumSoFar与否。我有点困惑基地的情况下，因为其结果不能超过我得尽可能接近的数量。

A recursive function with 2 parameters: an index that gives information about the element you're about to add (or not) and the sum so far. For every element I make a binary decision: add it to the sumSoFar or not. I'm a bit confused about the base cases since the result can't exceed the number I have to get as close as possible to.

谁能帮助我？

在此先感谢！

推荐答案

尝试某事是这样的：

bestsum = 0; recurisve(index, sum){ if index > max_index{ if sum is better than bestsum{ bestsum = sum } } recursive(index + 1, sum + element[index]); recursive(index + 1, sum); }

如果总和大于bestsum 更应该检查所有的条件来确定，有两个结果：之和 bestsum ， bestsum 比更好的结果之。

if sum is better than bestsum should check all condition to determine if, having two results: sum and bestsum, bestsum is better result than sum.