algorithm - 动态规划的问题

Question

我在理解动态规划方面遇到困难，所以我决定解决一些问题。我知道基本的动态算法，比如最长公共(public)子序列、背包问题，但我知道它们是因为我读过它们，但我不能自己想出一些东西:-(

例如，我们有自然数的子序列。我们可以加上或减去的每个数字。最后我们取这个和的绝对值。对于每个子序列，找到可能的最低结果。

in1: 10 3 5 4;输出 1: 2

in2: 4 11 5 5 5;输出 2:0

in3: 10 50 60 65 90 100;输出 3: 5

第三个的解释:5 = |10+50+60+65-90-100|

更糟糕的是，我的 friend 告诉我这是一个简单的背包问题，但我在这里看不到任何背包。动态规划是不是很难，或者只有我有大问题？

Answer 1

正如 amit 所指出的，该算法可以理解为 partition problem 的一个实例.对于简单的实现，请查看此 Python 代码:

def partition(A):
    n = len(A)
    if n == 0:
        return 0
    k, s = max(A), sum(A)/2.0
    table = [0 if x else 1 for x in xrange(n*k)]
    for i in xrange(n):
        for j in xrange(n*k-1, -1, -1):
            if table[j-A[i]] > table[j]:
                table[j] = 1
    minVal, minIdx = float('+inf'), -1
    for j in xrange(int(s)+1):
        if table[j] and s-j < minVal:
            minVal, minIdx = s-j, j
    return int(2*minVal)

当使用问题中的输入之一调用时:

partition([10, 50, 60, 65, 90, 100])

它将按预期返回 5。为了充分理解解决方案背后的数学原理，请查看此 examples并单击“平衡分区”链接。