python-3.x - 使用动态规划的数组分区

Question

我应该对二分法问题的动态规划实现应用什么修改来解决以下任务:

给定一个正整数数组作为输入，将其表示为 C。程序应决定是否可以将数组划分为两个相等和的子序列。您可以从数组中删除一些元素，但不是全部，以使此类分区可行。

示例:

假设输入是 4 5 11 17 9。如果我们删除 11 和 17，则可以进行两个分区。我的问题是我应该对我的两个分区实现进行哪些调整以确定是否可以进行两个分区(可能需要也可能不需要删除一些元素)或者即使删除一些元素也输出两个分区是不可能的。该程序应在 O(sum^2 * C) 时间内运行。

这是我在 Python 中的两个分区实现:

def two_partition(C):
    n = len(C)
    s = sum(C)
    
    if s % 2 != 0: return False
    
    T = [[False for _ in range(n + 1)] for _ in range(s//2 + 1)]
    for i in range(n + 1): T[0][i] = True
    
    for i in range(1, s//2 + 1):
        for j in range(1, n + 1):
            T[i][j] = T[i][j-1]
            if i >= C[j-1]:
                T[i][j] = T[i][j] or T[i-C[j-1]][j-1]
                   
    return T[s // 2][n]

例如，对于输入 [2, 3, 1]，预期输出为 {2,1} 和 {3}。这使得可以将数组划分为两个相等的子集。在这种情况下，我们不需要删除任何元素。在上面的 4 5 11 17 9 示例中，如果我们删除 11 和 17，这两个子集是可能的。这留下了 {4,5} 和 {9}。

Answer 1

创建一个 3 维数组，索引由第一个分区的总和、第二个分区的总和和元素数组成。T[i][j][k] 如果只有在可能有两个不相交的子集且总和分别为 i 和 j 时才为真前 k 个元素。

要计算它，您需要考虑每个元素的三种可能性。它要么出现在第一组或第二组中，要么被完全删除。在循环中为每个可能的总和组合执行此操作，生成所需的 O(sum ^ 2 * C) 数组。

要找到您的问题的答案，您需要检查的是存在一些总和 i 使得 T[i][i][n] 是真的。这意味着存在两个不同的子集，这两个子集的总和为 i，如问题所要求的。

如果您需要找到实际的子集，使用简单的回溯函数即可轻松实现。只需在 back_track 函数和递归中检查三种可能性中的哪一种是可能的。

这是一个示例实现:

def back_track(T, C, s1, s2, i):
    if s1 == 0 and s2 == 0: return [], []
    if T[s1][s2][i-1]:
        return back_track(T, C, s1, s2, i-1)
    elif s1 >= C[i-1] and T[s1 - C[i-1]][s2][i-1]:
        a, b = back_track(T, C, s1 - C[i-1], s2, i-1)
        return ([C[i-1]] + a, b)
    else:
        a, b = back_track(T, C, s1, s2 - C[i-1], i-1)
        return (a, [C[i-1]] + b)

def two_partition(C):
    n = len(C)
    s = sum(C)

    T = [[[False for _ in range(n + 1)] for _ in range(s//2 + 1)] for _ in range(s // 2 + 1)]
    for i in range(n + 1): T[0][0][i] = True

    for s1 in range(0, s//2 + 1):
        for s2 in range(0, s//2 + 1):
            for j in range(1, n + 1):
                T[s1][s2][j] = T[s1][s2][j-1]
                if s1 >= C[j-1]:
                    T[s1][s2][j] = T[s1][s2][j] or T[s1-C[j-1]][s2][j-1]
                if s2 >= C[j-1]:
                    T[s1][s2][j] = T[s1][s2][j] or T[s1][s2-C[j-1]][j-1]
    for i in range(1, s//2 + 1):
        if T[i][i][n]:
            return back_track(T, C, i, i, n)
    return False

print(two_partition([4, 5, 11, 9]))
print(two_partition([2, 3, 1]))
print(two_partition([2, 3, 7]))