7

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

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

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|

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

4

3 回答 3

5

正如阿米特所指出的，该算法可以理解为分区问题的一个实例。对于一个简单的实现，看看这个 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正如预期的那样，它将返回。为了充分理解解决方案背后的数学原理，请查看此示例并单击“平衡分区”链接。

于 2012-03-25T17:41:25.650 回答
2

这里的背包是weight = value = number为每个元素准备的。

你的界限W是1/2 * sum(elements)。

这个想法是 - 你想在不超过 的限制的情况下最大化你“选择”的数字数量1/2 * sum(elements)，这正是 的背包value=weight。

这个问题实际上是分区问题，是子集和问题的一个特例。

分区问题说：“是否有可能得到一个总和正好为一半的元素子集？”
从这里推导你的问题很简单——如果有，把这些当作+，而那些你没有当作 的-，你就会得到out = 0。[反之亦然]。因此，您描述的问题是分区问题的优化。

于 2012-03-25T17:16:33.370 回答
0

这与拔河中的问题相同，没有平衡团队规模的限制（不相关）： http ://acm.uva.es/p/v100/10032.html

我用自上而下的方法解决了这个问题。它适用于给定数字有上限的约束。你有上限还是数量不受限制？如果它们不受约束，我看不出如何用动态编程来解决这个问题。

于 2012-03-25T17:15:35.427 回答