5

喜んでお手伝いさせていただきます。

次の問題があります。

数値のリストseqと目標数値が与えられ、次の 2 つのことを記述する必要があります。

  1. Trueサブシーケンスの合計がターゲット数と等しいか、そうでない場合に返される再帰的なソリューションFalse。例：

    subset_sum([-1,1,5,4],0)   # True
subset_sum([-1,1,5,4],-3)  # False

  2. 次に、前のソリューションで書いたものを使用してソリューションを作成する必要がありますが、キーがタプルである辞書を使用するメモ化を使用します。 (len(seq),target)

番号1については、これまでに得たものです：

def subset_sum(seq, target):
    if target == 0: 
        return True
    if seq[0] == target:
        return True
    if len(seq) > 1:
        return subset_sum(seq[1:],target-seq[0]) or subset_sum(seq[1:],target)
    return False

私はそれが正しいかどうかわからないので、何らかの意見を得ることができれば感謝します.

番号 2 の場合:

def subset_sum_mem(seq, target, mem=None ):
    if not mem:
        mem = {}
    key=(len(seq),target)
    if key not in mem:
        if target == 0 or seq[0]==target:
            mem[key] = True
        if len(seq)>1:
            mem[key] = subset_sum_mem(seq[1:],target-seq[0],mem) or subset_sum_mem(seq[1:],target,mem)
        mem[key] = False

    return mem[key]

メモ化して正解を出すことができないので、ここでいくつかのガイダンスをいただければ幸いです。

喜んで手伝ってくれてありがとう！

4

3 に答える 3

1

参考までに、動的計画法を使用したソリューションを次に示します。

def positive_negative_sums(seq):
    P, N = 0, 0
    for e in seq:
        if e >= 0:
            P += e
        else:
            N += e
    return P, N

def subset_sum(seq, s=0):
    P, N = positive_negative_sums(seq)
    if not seq or s < N or s > P:
        return False
    n, m = len(seq), P - N + 1
    table = [[False] * m for x in xrange(n)]
    table[0][seq[0]] = True
    for i in xrange(1, n):
        for j in xrange(N, P+1):
            table[i][j] = seq[i] == j or table[i-1][j] or table[i-1][j-seq[i]]
    return table[n-1][s]
于 2012-01-26T21:37:46.050 に答える
0

私はこの変更されたコードを持っています:

def subset_sum(seq, target):
    left, right = seq[0], seq[1:]
    return target in (0, left) or \
        (bool(right) and (subset_sum(right, target - left) or subset_sum(right, target)))

def subset_sum_mem(seq, target, mem=None):
    mem = mem or {}
    key = (len(seq), target)
    if key not in mem:
        left, right = seq[0], seq[1:]
        mem[key] = target in (0, left) or \
            (bool(right) and (subset_sum_mem(right, target - left, mem) or subset_sum_mem(right, target, mem)))
    return mem[key]

これがうまくいかないテストケースをいくつか提供できますか?

于 2012-01-26T20:37:18.763 に答える
0

これは私が書く方法ですsubset_sum：

def subset_sum(seq, target):
    if target == 0:
        return True

    for i in range(len(seq)):
        if subset_sum(seq[:i] + seq[i+1:], target - seq[i]):
            return True
    return False

いくつかの例で機能しました：

>>> subset_sum([-1,1,5,4], 0))
True
>>> subset_sum([-1,1,5,4], 10)
True
>>> subset_sum([-1,1,5,4], 4)
True
>>> subset_sum([-1,1,5,4], -3)
False
>>> subset_sum([-1,1,5,4], -4)
False

正直なところ、私はそれをメモする方法を知りませんでした。

古い編集:any()いくつかのテストの後、遅いことがわかったので、ソリューションを削除しました!

更新：好奇心から、次のものも使用できますitertools.combinations：

from itertools import combinations

def com_subset_sum(seq, target):
    if target == 0 or target in seq:
        return True

    for r in range(2, len(seq)):
        for subset in combinations(seq, r):
            if sum(subset) == target:
                return True
    return False

これは、場合によっては動的プログラミングのアプローチよりもうまくいく可能性がありますが、他の場合にはハングします (再帰的なアプローチよりも優れています)。

于 2012-01-26T21:14:11.383 に答える