带负数的子集和
Subset sum with negative numbers
所以我有一个给定的 n 个正整数集合 C (c_1, ..., c_n)。任务是找到 C 的两个子集 A 和 B，其中 A 仅包含正数，B 仅包含 C 中数字的负数。两个子集 A 和 B 的总和应为数字 d (d总是积极的）。我需要找出是否有两个这样的子集，如果有，它们包含哪些数字。
For example: {3, 5, 6, 13, 24} // d = 12
=> solution: true: {5, 13} {-6}
我知道这是子集和问题的一个变体，我已经看到了类似问题的一些解决方案（负数的子集和），但我需要使用动态规划来解决这个问题。我见过的大多数解决方案都适用于递归，不适用于 DP。
我想我需要一个大小为 (n * n * d) 的 3D 布尔值 table 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)
我的想法是正确的还是我已经做错了什么？
一种方法是对由 (c_1,c_2,...,c_n,-c_1,-c_2,...,-c_n).
这将找到总和为 d 的子集（或证明 none 存在）。
将A设置为子集中的所有正数，将B设置为所有负数。
您可能还希望删除同时出现在 A 和 B 中的任何数字（例如，如果您在 A 中有一个 3，在 B 中有一个 -3，那么您可以在不改变总和的情况下删除这两个数字）。
所以我有一个给定的 n 个正整数集合 C (c_1, ..., c_n)。任务是找到 C 的两个子集 A 和 B，其中 A 仅包含正数，B 仅包含 C 中数字的负数。两个子集 A 和 B 的总和应为数字 d (d总是积极的）。我需要找出是否有两个这样的子集，如果有，它们包含哪些数字。
For example: {3, 5, 6, 13, 24} // d = 12
=> solution: true: {5, 13} {-6}
我知道这是子集和问题的一个变体，我已经看到了类似问题的一些解决方案（负数的子集和），但我需要使用动态规划来解决这个问题。我见过的大多数解决方案都适用于递归，不适用于 DP。
我想我需要一个大小为 (n * n * d) 的 3D 布尔值 table 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)
我的想法是正确的还是我已经做错了什么？
一种方法是对由 (c_1,c_2,...,c_n,-c_1,-c_2,...,-c_n).
这将找到总和为 d 的子集（或证明 none 存在）。
将A设置为子集中的所有正数，将B设置为所有负数。
您可能还希望删除同时出现在 A 和 B 中的任何数字（例如，如果您在 A 中有一个 3，在 B 中有一个 -3，那么您可以在不改变总和的情况下删除这两个数字）。