动态编程的问题

Question

我对理解动态编程有困难,所以我决定解决一些问题.我知道基本的动态算法,如最长的常见子序列,背包问题,但我知道它们因为我读过它们,但我不能自己想出一些东西:-(

例如,我们有自然数的子序列.我们可以使用加号或减号的每个数字.最后,我们取这个总和的绝对值.对于每个子序列,找到尽可能低的结果.

in1:10 3 5 4; out1:2

in2:4 11 5 5 5; out2:0

in3:10 50 60 65 90 100; out3:5

第3次解释:5 = | 10 + 50 + 60 + 65-90-100 |

更糟糕的是我的朋友告诉我这是简单的背包问题,但我在这里看不到任何背包.动态编程有些困难,还是只有我有很大问题？

Answer 1

正如amit所指出的,该算法可以理解为分区问题的一个实例.有关简单的实现,请查看此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按预期,它将返回.要完全理解解决方案背后的数学原理,请查看此示例并单击"平衡分区"链接.