Common subset sum fast algorithm
-
03-11-2019 - |
Pregunta
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)?
No hay solución correcta
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange