Is there any way to determine if a given Sum
can be formed by taking minimum number of elements of a set/array
.
Repetition of array elements is allowed.I tried brute force taking a map n dovetailing through.
Eg. {1,2,3,4,5}
and the sum to be formed is 8. Then {3,5} or {4,4}
.
Therefore the size of minimum set is 2
,repitition is allowed.
[** Note: Even if you take same element twice it is counted as two.]
Finding Subset-Sum with low cardinality
0
$\begingroup$
algorithms
-
0Subset-Sum is the name of a problem where numbers can be taken at most once, which is actually harder than the problem you are describing, so the title is confusing. I'm also not sure what you mean by low cardinality, or how efficient of a solution you are looking for. You're really interested in non-negative solutions to a diophantine equation. – 2012-12-02
1 Answers
0
SUBSET-SUM (mentioned by William Macrae above) reduces to your problem in polynomial time and your problem is NP-complete. you can only look for an efficient heuristic to approximate the solution.
This is rather a comment. only allowing me to write answers here on this site-- not comments. hope this helps.