Find solution
what is the difference between sum of first n primes and prime(prime(n?

Given a set of [math]n[/math] natural numbers, find the two subsets of 'k' numbers, which sum is [math]S_k[/math] , that minimize the difference between these sums. How do you solve it with dynamic programming?

  • Given the set [math] \{ a_1, ..., a_n \} [/math] where [math]a_i \in \mathbb{N}[/math], find two subset [math]A[/math] and [math]B[/math] such that: [math]A \cap B = \emptyset[/math] [math] card(A) = card(B) = k > 0[/math] where [math] 2k \le n [/math] [math]\min_{ \forall A,B \subset \{ a_1, ..., a_n \} \wedge \text{above conditions}} \left | \sum_{\forall x \in A} x - \sum_{\forall w \in B} w  \right |[/math] I tried serveral ways but all of these end in a sort of backtracking :( . update: i already solved a single instance of a partition problem (see or http://people.csail.mit.edu/bdean/6.046/dp/ ) where the partitions have the same size and the same sum, but i can't get any help from that solution :( . update2: i solved the general instance of partition problem as follow, but i got any clue to solve the problem in the question. My solution still ends in a sort of backtracking. The key for balanced partition problem is: if the sum of elements of the set is S, then we need to found the partition which the sum of its elements is close to [math]S' = \left \lceil S/2 \right \rceil[/math], to obtain the minimum difference between this partition and the complementary one. So, extending the knapsack solution in terms of dynamic programing we have: w(i,j,k) i - the partial problem consider only the first i elements in the set j - the partial problem allow only a maximum sum of j k - the partition found as solution of the partial problem contains k elements of the first i elements considered. i.value - the value of the i-th element so: if ( i.value > j ) then w(i,j,k) = w(i-1,j,k) //we can't use the i-th element in the solution if (i.value <= j) then w(i,j,k) = max { w(i-1,j,k), //the better solutions still exclude i w(i-1,j-i.value,k-1)+i.value} //OR given the space for i (j-i.value) a solution with i and //the best solution with other elements for the remaining space //is the best whole solution the inizialization values are: w(0,0,k) = -1 //nonsense w(0,j,0) = 0 //no elements w(i,0,0) = 0 //no weight w(i,j,0) = 0 //no elements in the solution w(0,j,k) = -1 //nonsense the values are: i = 0,...,n ; j = 0,...,S' ; k = 0,...,ceil(n/2); //since n can be odd and if the block closest to S' has floor(n/2)+k elements, then //the best block found by the recurring formula above is that with ceil(n/2)-k elements //that has the complementary block mentioned before. Then the best partition close to [math]S' = \left \lceil S/2 \right \rceil[/math] is found as the maximum value on the row: [math]w(n,S',k)[/math] where 'k' is free to variate. (the maximum is one block, the complementary is the second block of the partition)

  • Answer:

    Define [math]D[i,j,k] = true[/math] iff there exists some [math]A,B \subset \{a_1, ..., a_i\}[/math] such that [math]A \cap B = \emptyset[/math], [math]|A| = |B| + j[/math] with [math]j \geq 0[/math], and [math]\sum_{x \in A}{x} = k+\sum_{y \in B}{y}[/math],  We require that at least one of A and B is nonempty. Note that [math]k[/math] may be either positive or negative. Then a recurrence which can be used for dynamic programming is [math]D[i,j,k] = D[i-1,j,k]   \lor [/math]    [math] D[i-1, j-1, k - a_{i}]   \lor [/math]    [math] D[i-1, j+1, k + a_{i}]   \lor [/math]    [math] ( j = 1 \land D[i-1,0,-(k-a_{i})] )   \lor [/math]    [math] ( j = 1 \land k = a_{i} )[/math] The cases here correspond to (1) not using [math]a_i[/math], (2) adding [math]a_i[/math] to A, (3) adding [math]a_i[/math] to B, (4) adding [math]a_i[/math] to B so that it becomes the larger set, or (5) setting [math]A={a_i}[/math] and [math]B=\emptyset[/math]. For example, if D[8, 0, 4] is true and [math]a_i = 5[/math], then D[9, 1, 9] must be true as well, and so is D[9, 1, 1].  (I haven't implemented the code, I've just paper-prototyped it, so I may have a sign error somewhere...) After calculating the recurrence values starting at [math]i=1[/math] and concluding with [math]i=n[/math], examine the true values [math]D[n,0,k][/math] and pick the [math]k[/math] with lowest absolute value.  This is the solution to the optimization problem.  Annotating each D with a "parent" pointer (there may be multiple but we only need one) will let us reconstruct the A and B sets. The run time of this algorithm is not particularly good.  We can bound the absolute value of [math]k[/math] to half the sum of the set, so the run time should be no worse than [math]O(n^{2}N)[/math], and probably better in practice by using hashes to store [math]k[/math]'s rather than an array.

Mark Gritter at Quora Visit the source

Was this solution helpful to you?

Other answers

This is very close to asking for an approximation algorithm to the http://en.wikipedia.org/wiki/Partition_problem.  The only difference is that the partition problem doesn't require the two sets to be of equal size.  Perhaps you could gain some insight by looking at solutions to the partition problem.

Justin Rising

's approach is indeed the right way to think about the problem. I'll give a simpler (but less efficient solution) and then refine it into a solution which is essentially the one gave. Let's define [math]G[i,j,S_A,S_B] = True [/math] if there an assignment to sets [math]A[/math] and [math]B[/math] using only elements of [math]a_1,a_2,...,a_i[/math] such that [math]A \cap B = \emptyset [/math] and [math]|A|-|B|=j[/math] and [math]\sum\limits_{x \in A}{} x = S_A[/math] and [math]\sum\limits_{y \in B}{} y = S_B[/math]. How do we obtain [math]G[i,j,S_A,S_B][/math] recursively? Well, we can use the following recurrence (ignoring base cases) [math]G[i,j,S_A,S_B] = G[i-1,j,S_A,S_B] [/math] OR [math] G[i-1,j-1,S_A-a_i,S_B] [/math] OR [math] G[i-1,j+1,S_A,S_B-a_i] [/math] what this means in plain english is that we have three possible ways of using the element [math]a_i[/math]. We can: Not add it to [math]A[/math] or [math]B[/math] i.e. [math]G[i-1,j,S_A,S_B][/math] Add it to [math]A[/math] only i.e. [math]G[i-1,j-1,S_A-a_i,S_B][/math] Add it to [math]B[/math] only i.e. [math]G[i-1,j+1,S_A,S_B-a_i][/math] We must, in fact, obtain [math]G[i,j,S_A,S_B][/math] in one of the three ways above. Once we have computed all  [math]G[i,j,S_A,S_B][/math]'s, we can find the corresponding [math]S_A[/math] and [math]S_B[/math] with minimum difference by going through our table and looking at entries in [math]G[n,0,S_A,S_B][/math] which are [math]True[/math] So how can we simplify this? That's where 's ideas come in. Instead of keeping track of [math]S_A[/math] and [math]S_B[/math] separately, why not just combine them instead? Since we are ultimately interested in [math]|S_A-S_B|[/math], we can as well only keep track of [math]S_A - S_B[/math]. So, let's redefine our recurrence. Let's define [math]G[i,j,k][/math] to be the same as above except that this time, we only keep track of the difference between [math]S_A[/math] and [math]S_B[/math]. i.e. [math]k = S_A-S_B[/math]. Our new recurrence becomes, [math]G[i,j,k] = G[i-1,j,k] \text{ OR } [/math] [math]G[i-1,j-1,k-a_i] \text{ OR }  G[i-1,j+1,k+a_i][/math] Well, not quite. The reason for this is that it is perfectly possible to obtain our intended set by swapping [math]A[/math] and [math]B[/math] when the set sizes are equal. Hence we can obtain our desired assignment by using an assignment whose [math]k[/math] value might be of opposite sign. That's why the other term [math]G[i-1,0,-k+a_i][/math] is included. Note that this wasn't an issue previously, because we clearly defined what [math]S_A[/math] and [math]S_B[/math] are. Now, the full recurrence becomes: [math]G[i,j,k] = G[i-1,j,k] [/math] [math] \text{ OR }  G[i-1,j-1,k-a_i] [/math] [math]\text{ OR }  G[i-1,j+1,k+a_i] \text{ OR } [/math] [math] (G[i-1,0,-k+a_i] \text{ AND }  j=1)[/math]

Obinna Okechukwu

Related Q & A:

Just Added Q & A:

Find solution

For every problem there is a solution! Proved by Solucija.

  • Got an issue and looking for advice?

  • Ask Solucija to search every corner of the Web for help.

  • Get workable solutions and helpful tips in a moment.

Just ask Solucija about an issue you face and immediately get a list of ready solutions, answers and tips from other Internet users. We always provide the most suitable and complete answer to your question at the top, along with a few good alternatives below.