Geek Answers Handbook

SUM precisely using a solution of K elements

Problem: in a given array with N numbers, find a subset of size M (exactly M elements) equal to SUM.

I am looking for a solution for dynamic programming (DP) for this problem. Basically, to understand the matrix based approach. I wrote the program below, but did not add memoization, as I am still wondering how to do this.

#include <stdio.h> #define SIZE(a) sizeof(a)/sizeof(a[0]) int binary[100]; int a[] = {1, 2, 5, 5, 100}; void show(int* p, int size) { int j; for (j = 0; j < size; j++) if (p[j]) printf("%d\n", a[j]); } void subset_sum(int target, int i, int sum, int *a, int size, int K) { if (sum == target && !K) { show(binary, size); } else if (sum < target && i < size) { binary[i] = 1; foo(target, i + 1, sum + a[i], a, size, K-1); binary[i] = 0; foo(target, i + 1, sum, a, size, K); } } int main() { int target = 10; int K = 2; subset_sum(target, 0, 0, a, SIZE(a), K); }

Does the lower recursive solution make sense?

Let DP [SUM] [j] [k] be summed with SUM with exactly K elements selected from 0 to j elements.

  DP[i][j][k] = DP[i][j-1][k] || DP[ia[j]][j-1][k-1] { input array a[0....j] }

Base cases:

 DP[0][0][0] = DP[0][j][0] = DP[0][0][k] = 1 DP[i][0][0] = DP[i][j][0] = 0

This means that we can either consider this element (DP [ia [j]] [j-1] [k-1]) or we will not consider the current element (DP [i] [j-1] [K]) . If we consider the current element, k decreases by 1, which reduces the elements that must be taken into account, and the same thing happens when the current element is not considered, i.e. K does not decrease by 1.

+4
source share
2 answers

Your decision looks right.

Right now, you basically give up all the options and print every solution. If you want only one solution, you can add the flag that you set when one solution was found, and check before proceeding with recursive calls.

For memoization, you must first get rid of the binary array, after which you can do something like this:

 int memo[NUM_ELEMENTS][MAX_SUM][MAX_K]; bool subset_sum(int target, int i, int sum, int *a, int size, int K) { if (sum == target && !K) { memo[i][sum][K] = true; return memo[i][sum][K]; } else if (sum < target && i < size) { if (memo[i][sum][K] != -1) return memo[i][sum][K]; memo[i][sum][K] = foo(target, i + 1, sum + a[i], a, size, K-1) || foo(target, i + 1, sum, a, size, K); return memo[i][sum][K] } return false; }

Then look at memo[_all indexes_][target][K] . If so, then there is at least one solution. You can save additional information to get this next solution, or you can iterate with i from found_index - 1 to 0 and check for which i you have memo[i][sum - a[i]][K - 1] == true . Then take it and so on. This will allow you to restore the solution using only the memo array.

+3
source

As far as I understand, if you need to check only the possibility of input, the problem can be solved using a two-dimensional state space

 bool[][] IsFeasible = new bool[n][k]

where IsFeasible[i][j] is true if and only if there is a subset of 1 to i elements that are summed to the accuracy j for each

 1 <= i <= n 1 <= j <= k

and for this state space the recurrence relation

 IsFeasible[i][j] = IsFeasible[i-1][ka[i]] || IsFeasible[i-1][k]

where the left side of the or-operator || corresponds to the choice of the ith element, and the right side does not correspond to the choice of the ith element. The actual selection of items can be obtained by returning or supporting information stored during the evaluation.

0
source

More articles:


All Articles