java - 带负数的子集和

Question

所以我有一个由 n 个正整数 (c_1, ..., c_n) 组成的给定集合 C。任务是找到 C 的两个子集 A 和 B，其中 A 仅包含正数，B 仅包含 C 中数字的负数。两个子集 A 和 B 的总和应为数字 d (d总是积极的)。我需要找出是否有两个这样的子集，如果有，它们包含哪些数字。

例如:{3, 5, 6, 13, 24}//d = 12
=> 解决方案:真:{5, 13} {-6}

我知道这是子集和问题的一个变体，我已经看到了类似问题的一些解决方案(带负数的子集和)，但我需要使用动态规划来解决这个问题。我见过的大多数解决方案都适用于递归，而不适用于 DP。

我想我需要一个大小为 (n * n * d) 的 3D boolean 表 S(i,j,k)。但是 S(i,j,k) 什么时候为真什么时候为假呢？因为我总是需要检查使用 k 数计算总和的所有可能方法，其中它们可以是正数也可以是负数(例如:对于 4 个数字 {1,2,3,4} 有 2^4 种排列方式他们:1 + 2 + 3 + 4, 1 - 2 + 3 + 4, 1 - 2 - 3 + 4, ..., -1 + 2 - 3 - 4, 1 - 2 - 3 - 4)

我的想法是正确的还是我已经做错了什么？

Answer 1

一种方法是对由 (c_1,c_2,...,c_n,-c_1,-c_2,...,-c_n) 组成的集合使用标准动态规划子集求和算法。

这将找到总和为 d 的子集(或证明不存在)。

将 A 设置为子集中的所有正数，将 B 设置为所有负数。

您可能还希望删除同时出现在 A 和 B 中的任何数字(例如，如果您在 A 中有 3，在 B 中有 -3，那么您可以在不改变总和的情况下删除两者)。