0

重複の可能性:
サブセット和アルゴリズム

私は理解できない非常に簡単な問題を抱えています。セットの組み合わせを作成することで、可能な限り近づける必要のある数値と値の配列が与えられます。このアルゴリズムは再帰的に行う必要があります。結果は指定された数を超えることはできません。

たとえば、{6、9、4、2、7}の配列があり、14にできるだけ近づける必要がある場合、結果は13になります(要素9と4を選択することにより)。

これは私がこれまでに持っているものです:

2つのパラメーターを持つ再帰関数:追加しようとしている(または追加しない)要素に関する情報と、これまでの合計を提供するインデックス。すべての要素について、私はバイナリの決定を行います。それをsumSoFarに追加するかどうか。結果は私ができるだけ近づけなければならない数を超えることができないので、私は基本的なケースについて少し混乱しています。

誰かがこれで私を助けることができますか?

前もって感謝します!

4

1 に答える 1

1

このようにsthを試してください:

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);
}

if sum is better than bestsumすべての条件をチェックして、2つの結果があるかどうかを判断する必要があります:sumbestsumbestsumが。よりも良い結果ですsum

于 2012-12-19T10:45:37.950 に答える