使用动态规划的数组分区

Question

我应该对两个分区问题的动态规划实现应用什么修改来解决以下任务：

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

例：

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

下面是我在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

我快速调整了代码，用于搜索三个相等和的子集以解决给定的问题。

算法试图将每个项目A[idx]放在第一个袋子里，或者放在第二个袋子里（两个都是真实的袋子）或者放在第三个（虚假的）袋子里（忽略的项目）。真实袋子里的初始值（可用空间）是总和的一半。这种方法原封不动地具有指数复杂性（具有3^N叶子的决策树）

但是有很多重复的分布，所以我们可以记住一些状态而忽略分支，所以使用了一种动态规划记忆。这里提到的状态是当我们使用从最后一个索引到< code>idx的项目时，实际行李中的可用空间的集合。

状态存储的可能大小可能达到N*和/2*和/2

工作德尔菲代码（未经彻底测试，似乎有一个忽略项目输出的错误）

function Solve2(A: TArray<Integer>): string;
var
  Map: TDictionary<string, boolean>;
  Lists: array of TStringList;
  found: Boolean;
  s2: integer;

function CheckSubsetsWithItem(Subs: TArray<Word>; idx: Int16): boolean;
var
  key: string;
  i: Integer;
begin
    if (Subs[0] = Subs[1]) and (Subs[0] <> s2) then begin
      found:= True;
      Exit(True);
    end;

    if idx < 0 then
      Exit(False);

   //debug map contains current rests of sums in explicit representation

    key := Format('%d_%d_%d', [subs[0], subs[1], idx]);

    if  Map.ContainsKey(key) then
       //memoisation
       Result := Map.Items[key]
    else begin
        Result := false;
        //try to put A[idx] into the first, second bag or ignore it
        for i := 0 to 2 do begin
           if Subs[i] >= A[idx] then begin
            Subs[i] := Subs[i] - A[idx];
            Result := CheckSubsetsWithItem(Subs, idx - 1);
            if Result  then begin
              //retrieve subsets themselves at recursion unwindning
              if found then
                 Lists[i].Add(A[idx].ToString);
              break;
            end
            else
              //reset sums before the next try
              Subs[i] := Subs[i] + A[idx];
           end;
        end;
        //remember result - memoization
        Map.add(key, Result);
    end;
end;


var
  n, sum: Integer;
  Subs: TArray<Word>;
begin
  n := Length(A);
  sum := SumInt(A);
  s2 := sum div 2;
  found := False;

  Map := TDictionary<string, boolean>.Create;
  SetLength(Lists, 3);
  Lists[0] := TStringList.Create;
  Lists[1] := TStringList.Create;
  Lists[2] := TStringList.Create;

   if CheckSubsetsWithItem([s2, s2, sum], n - 1) then begin
     Result := '[' + Lists[0].CommaText + '], ' +
               '[' + Lists[1].CommaText + '], ' +
               ' ignored: [' + Lists[2].CommaText + ']';
   end else
     Result := 'No luck :(';
end;



begin
   Memo1.Lines.Add(Solve2([1, 5, 4, 3, 2, 16,21,44, 19]));
   Memo1.Lines.Add(Solve2([1, 3, 9, 27, 81, 243, 729, 6561]));
end;

[16,21,19], [1,5,4,2,44],  ignored: [3]

No luck :(

Answer 2

为了确定这是否可行，请在两个部分之间保留一组独特的差异。对于每个元素，迭代到目前为止看到的差异；减去并添加元素。我们正在寻找差异0。

4 5 11 17 9

0 (empty parts)

|0 ± 4| = 4

set now has 4 and empty-parts-0

|0 ± 5| = 5
|4 - 5| = 1
|4 + 5| = 9

set now has 4,5,1,9 and empty-parts-0

|0 ± 11| = 11
|4 - 11| = 7
|4 + 11| = 15
|5 - 11| = 6
|5 + 11| = 16
|1 - 11| = 10
|1 + 11| = 12
|9 - 11| = 2
|9 + 11| = 20

... (iteration with 17)

|0 ± 9| = 9
|4 - 9| = 5
|4 + 9| = 13
|5 - 9| = 4
|5 + 9| = 14
|1 - 9| = 8
|1 + 9| = 10
|9 - 9| = 0

Bingo!

Python代码：

def f(C):
  diffs = set()

  for n in C:
    new_diffs = [n]

    for d in diffs:
      if d - n == 0:
        return True
      new_diffs.extend([abs(d - n), abs(d + n)])

    diffs = diffs.union(new_diffs)

  return False

输出:

> f([2, 3, 7, 2])

=> True

> f([2, 3, 7])

=> False

> f([7, 1000007, 1000000])

=> True

Answer 3

创建一个由第一个分区之和、第二个分区之和和和元素数索引的3维数组。T[i][j][k]如果仅当有可能有两个不相交的子集和i

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

要找到问题的答案，您只需要检查是否存在某个和i，使得T[i][i]][n]为真。这意味着有两个不同的子集，根据问题的要求，这两个子集的总和都为i。

如果您需要找到实际的子集，使用一个简单的回溯函数很容易做到这一点。只需检查back_track函数和recurse中三种可能性中的哪一种是可能的。

这是一个示例实现：

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]))