Suppose of I two sets of $n$ integers bounded in $[-B,B]$. The integers are $$a_1,\dots,a_n$$ $$b_1,\dots,b_n$$

I want to find if there is a common subset $I\subseteq\{1,\dots,n\}$ such that $$\sum_{i\in I}a_i=0$$$$\sum_{i\in I}b_i=0$$

This problem is $NP$-complete.

Is there a pseudo polynomial time algorithm with complexity for this problem like the regular subset sum problem on bounded integers which has an $O(B^2)$ algorithm (https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution)?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top