这是背包问题的一个例子吗？

Question

我有一个看似简单的问题，但我正在努力解决。转向Google，看来这可能是背包问题的一个变体，但我在将这些解决方案映射到此特定问题时遇到了麻烦。

比方说，我有两个正整数列表，A和B。我想找到代表这两个列表之间最大公共和的值。

A: [6, 1]
B: [5, 3, 1]

这里答案是6，因为这是两个列表中可以共同创建的最大和（通过删除列表A中的1和删除列表B中的3）。

我可以在O（2 ^ n）中天真地解决这个问题，但我假设通过动态编程有一种效率更高的方法，尽管dp不是我的强项。

这是背包问题吗？关于如何将经典背包问题映射到此两列表问题的任何指示？

Answer 1

这可以在O(nW)中解决，其中n是所有元素的计数，W是列表中所有元素的总和。

分别处理每个列表。如果存在第一个列表的前dp1[i][j]个元素的子集，且其总和等于i（j，0 <= i <= n1），则使0 <= j <= W1为真。 dp1可以使用递归公式填充：

• [dp1[0][0]是true
• [dp1[0][j]是false（j != 0）
• EDIT：dp1[i][0]是true（i != 0）
• dp1[i][j]为true，如果：
  • （[j >= list.get(i) AND dp[i - 1][j - list.get(i)]是true）
  • 或dp[i - 1][j]是true

然后为第二个列表填充dp2[i][j]。然后只需找到S和dp1[n1][S]均为dp2[n2][S]的最大数量true。