Ok, this is a funny problem.
In first place, I suspected this could be a NP-complete
problem but later I suspected I was mistaken because some "backdoor" algorithm might exist. However, this article
on the problem states that it is indeed a NP-complete
one. But only when I learned from the same article that there are different Knapsack and Knapsack-like problems, only then I paid closer attention to the formulation of the present Question. Silly me!
Well, this is neither basic nor generalized Knapsack problem, so let's consider this is a Knapsack-like problem, rather simplified. The formulation is contradictory: the words "I need some help solving an algorithm in C#" hint that general algorithm is required, but is this case, why giving the following constraints:
W = 15, N = 17, S = [1, 2, 4, 9]
? With this figures, formally speaking, algorithm is not required, proven solution would be the answer.
As my mood of relaxing after the Christmas Eve party does not inspire much enthusiasm for working at the general algorithm, let' first think about the formal solution with constraints.
Ok, we can immediately see that there is no solution
: as minimum S=1, minimum sum of N weights is equal to N*1 = N = 17, which is more than W = 15. Now, follow the most delicate and hard-to-understand inference: if minimum sum of N weights is less then W, any other combination of N weights is more than W => no combination of N weights is equal to W =>
Aha, now we can see that the inquirer is locked in the corner. I do understand that shaden2009
could have done a simple mistake; and the figures could be different. Who knows? Slip of a hand. May be W and N should be swapped; then the problem is solvable... -- too late!
The proof is presented, and shaden2009
assumed sole responsibility for the formulation of the problem.
In this way, shaden2009
, being a undoubtedly, honest person (we all are supposed to be honest aren't we?) has nothing to do but accept my answer now.
If there is more accurate formulation of the problem which would make it more sensible, we would certainly enjoy considering it (shall we?), but that should be another question. The present answer should be accepted; and the present question closed.
Thank you for attention!
Take it easy!
Best wishes in New Year, everyone!