0

たとえば、4、10、4、7 のようなシーケンスが与えられた場合、10 を取得する必要があります。答えは 4+10-4=10 です。どのようなアプローチを使用することをお勧めします。DPで解決できますか？ありがとうございました！

4

2 に答える 2

3

私の頭に浮かぶ動的計画法のアルゴリズムに最も近いものは、次の (Python) です。

def find_number(numbers, goal):
    # sum 0 can be reached with empty sequence
    found = {0: []}
    # iterate over all numbers in the list
    for n in numbers:
        # update dict of found numbers with m+n and m-n for each m in found
        found = dict([(m + n, path + [+n]) for (m, path) in found.items()] +
                     [(m - n, path + [-n]) for (m, path) in found.items()])
        # check whether the goal number is among them
        if goal in found:
            return found[goal]

再帰的なツリー トラバーサル アルゴリズム以外に、これには、中間結果 (シーケンス内の特定の数まで到達できる数) がハッシュ マップに格納されるため、二重作業を回避できるという利点があります。(つまり、最初のk数の複数の組み合わせを使用して特定の数に到達できる場合、そのうちの 1 つだけがマップに格納されます。) 加算または減算しても目標に到達できない可能性のある中間結果を破棄することにより、さらに最適化を行うことができます。残りのすべての数の合計。

それでも、再帰的アプローチと同様に、foundマップのサイズは反復ごとに 2 倍になる可能性があるため、最悪の場合の複雑さ (時間と空間の両方) およびおそらく平均的な場合の複雑さでさえ、リストの長さにおいて指数関数的です。

于 2013-02-12T21:31:11.150 に答える
1

JavaScript での例を次に示します。必要に応じて、シーケンス内の番号を変更できます。一致した場合にのみ結果が記録されます。

var sequence = [4, 10, 4, 7],
    tree = []

for (var i=0; i<sequence.length; i++){
  tree.push([sequence[i], -sequence[i]])
}

function findMatch(arr, match, numSoFar, path, iterations){
  var numSofar1 = numSoFar + arr[iterations][0],
      numSofar2 = numSoFar + arr[iterations][1],
      path1 = path + (arr[iterations][0] > 0 && iterations > 0 ? "+" : "") 
              + String(arr[iterations][0]),
      path2 = path + (arr[iterations][1] > 0 && iterations > 0 ? "+" : "") 
              + String(arr[iterations][1])

  if (numSofar1 == match) console.log(path1)
  else if (numSofar2 == match) console.log(path2)
  else if (iterations < arr.length-1){
    findMatch(arr, match, numSofar1, path1, iterations + 1)
    findMatch(arr, match, numSofar2, path2, iterations + 1)
  }
}

findMatch(tree, 10, 0, "", 0)
于 2013-02-12T20:41:24.327 に答える