It looks good. Have you done some experiments to test its efficiency? Maybe (1) is not such a strong branch-cutting condition as you think. See sequence like below: P[p], P[1]*P[2]*...*P[p-1] *(P[p]-1), P[1]*P[2]*...*P[p-1] *(P[p]-2) , ..., P[1]*P[2]*...*P[p-1] *(1) It need branch on every element of the right half. Meanwhile the absolute sum of all elements is a polynomial of all P[i].
On Nov 11, 2007 12:23 PM, Yao Ziyuan <[EMAIL PROTECTED]> wrote: > > 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 > > > > > -- Hongcheng Zhu --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
