带负数的子集和

所以我有一个给定的C个n个正整数(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布尔表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)

我的想法是正确的还是我做错了什么?

回答(1)

2 years ago

一种方法是在由(c_1,c_2,...,c_n,-c_1,-c_2,..., - c_n)组成的集合上使用标准动态编程子集和算法 .

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

将A设置为子集中的所有正数,将B设置为所有负数 .

您可能还希望删除A和B中出现的任何数字(例如,如果A中有3,B中有-3,那么您可以删除两者而不更改总和) .