子集和递归获得尽可能接近到一个给定数目 [英] Subset sum recursively to get as near as possible to a given number

问题描述

可能重复：
  子集和算法

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

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.

这篇关于子集和递归获得尽可能接近到一个给定数目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！