An effective search algorithm for the subset sum problem
Problem: There are n integers N_1, N_2, ..., N_n; we wonder if the sum
of some or all of these integers (a subset sum) is 0.
Solution:
Suppose
(1) There are p different prime numbers P_1, P_2, ..., P_p;
(2) P_1 * P_2 * ... * P_p > the largest of the absolute values of all
subset sums;
(3) There is a subset sum M satisfying: M mod P_1 = 0; M mod P_2 =
0; ...; M mod P_p = 0;
Then
M must be 0.
For each P_i (i=1..p), use dynamic programming to compute the values
of "all subset sums mod P_i" and store them in the arrays s_mod_P_i[n]
[P_i]. For example, for the prime number P_1, we get an dynamic
programming array s_mod_P_1[n][P_1], where s_mod_P_1[i][j] = true
would mean there exists a subset among N_1, N_2, ..., N_i whose sum
mod P_1 equals j.
With these p arrays s_mod_p_i (i=1..p), we can use search to restore
an M and one of its addition expression in terms of N_1, N_2, ...,
N_n, or prove that M doesn't exist:
Suppose M exists, and we have an initial condition s_mod_P_i[n][0] =
true; (i=1..p)
We want to determine whether an addition expression of M includes N_n
as an addend, then
either (1) N_n is included, i.e. s_mod_P_i[n-1][(0 - P_i) mod P_i] =
true; (i=1..p)
or (2) N_n is not included, i.e. s_mod_P_i[n-1][0] = true; (i=1..p)
or (3) both (1) and (2) are true;
or (4) neither (1) or (2) is true.
If (4) is true, it means M doesn't exist for the current search path
and we must backtrack;
If (1) or (2) is true (and (3) is not true), it means there is only
one outlet for the current search path and we don't have to branch
out;
If (3) is true, it means we must branch out 2 branches for the current
search path;
For (1), (2) or (3), we step forward to determine whether N_(n-1) can
be included in an addition expression of M.
This search algorithm has a strong branch-cutting condition in (1) and
is supposed to save a lot of time.
I originally think this is a dynamic programming algorithm and thanks
to Lin He who pointed out that there is actually a possibility for (3)
and suggested it can still be an efficient search algorithm.
Your comments are appreciated in advance.
Regards,
Yao Ziyuan
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
