这是背包问题的一个例子吗？
Is this an instance of the knapsack problem?
我遇到了一个看似简单的问题，但我正在努力解决它。转向 Google 看来这可能是背包问题的变体，但我无法将这些解决方案映射到这个特定问题。
假设我有两个正整数列表 A 和 B。我想找到表示这两个列表之间最大公和的值。
A: [6, 1]
B: [5, 3, 1]
这里，答案是6，因为这是两个列表中可以共同创建的最大总和（通过删除列表A中的1和删除列表B中的3）。
我可以在 O(2^n) 中天真地解决这个问题，但我假设通过动态规划有一种更有效的方法，尽管 dp 不是我的强项。
这是背包问题吗？关于我应该如何将经典背包问题映射到这个双列表问题的任何指示？
这可以在 O(nW) 中解决，其中 n 是所有元素的计数，W 是列表中所有元素的总和。
分别处理每个列表。如果第一个列表的第一个 i 元素有一个子集，则令 dp1[i][j] 为真，其总和等于 j (0 <= i <= n1, 0 <= j <= W1) . dp1 可以使用循环公式填充：
dp1[0][0] 是 truedp1[0][j] 是 false (j != 0)- 编辑：
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.
我遇到了一个看似简单的问题，但我正在努力解决它。转向 Google 看来这可能是背包问题的变体，但我无法将这些解决方案映射到这个特定问题。
假设我有两个正整数列表 A 和 B。我想找到表示这两个列表之间最大公和的值。
A: [6, 1]
B: [5, 3, 1]
这里，答案是6，因为这是两个列表中可以共同创建的最大总和（通过删除列表A中的1和删除列表B中的3）。
我可以在 O(2^n) 中天真地解决这个问题，但我假设通过动态规划有一种更有效的方法，尽管 dp 不是我的强项。
这是背包问题吗？关于我应该如何将经典背包问题映射到这个双列表问题的任何指示？
这可以在 O(nW) 中解决，其中 n 是所有元素的计数，W 是列表中所有元素的总和。
分别处理每个列表。如果第一个列表的第一个 i 元素有一个子集，则令 dp1[i][j] 为真，其总和等于 j (0 <= i <= n1, 0 <= j <= W1) . dp1 可以使用循环公式填充：
dp1[0][0]是truedp1[0][j]是false(j != 0)- 编辑：
dp1[i][0]是true(i != 0) dp1[i][j]是true如果：- (
j >= list.get(i)ANDdp[i - 1][j - list.get(i)]是true) - 或
dp[i - 1][j]是true
- (
然后为第二个列表填写dp2[i][j]。然后找到 S 的最大数量 dp1[n1][S] 和 dp2[n2][S] 都是 true.