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 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 -~----------~----~----~----~------~----~------~--~---