I made a mistake while constructing worst case input. Just ignore it. On Nov 14, 2007 11:50 AM, hongcheng zhu <[EMAIL PROTECTED]> wrote:
> 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 -- Follow your heart! --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
