Given N elements, find best permutation closest to Σ

[StreamKid]

I read from file a wanted number, Σ. Then i read N( # of numbers ), and N numbers. I have to create a program that has to find nearest value to Σ that can be "made" using( at maximum ) all the numbers( N ). I must use as few as possible numbers.

Example:
Σ=10, N=6
n1=19, n2=1, n3=8, n4=7, n5=1, n6=2
Wanted number is 10. Nearest value that can be made: we can achieve doing 10.
We can make 10 using:
i) n3 + n6 { 8 + 2 }
ii) n3 + n2 + n5 { 8 + 1 + 1 }
iii) n4 + n5 + n6 { 7 + 1 + 2 }

since ii and iii use 3 numbers to make 10 and i uses 2, the right is i
--------------------------------------------------------------------------------------
that's basically the problem. i 've came up with a solution:
i find the closest number to Σ, i name it x. if any number if larger than Σ, i just "ignore".
I do Σ % x. if, say Σ=100 and x = 90, i get 10. then i find the closest number to 10, and so on.
i 've solved the problem in this way, but that's not always the right solution. does anybody have any idea, any clue or any-something to help???
'd appreciate it much..
tia, streamkid :)

[Yves M]

Is there only the plus operation? I.e. you can't do 8*2 + 1 e.g.? If so, then the problem is equivalent to the knapsack problem, which is NP-complete. I.e. there is no known polynomial algorithm that is guaranteed to find the correct solution(s).

There is a good discussion about this exact problem on this page (http://en.wikipedia.org/wiki/Subset_sum_problem).

In practise, if the numbers are as small as the ones you described, the obvious solution of trying each possibility will probably be fast enough though.

[StreamKid]

hey, thanks for the reply.
as given in the problem,
100 <= Σ < 10000
10 <= N < 1000
1 < E <= 900, where E the max size of an element..

I don't know if these are small..
I 've also thinked of brute-forcing all permutations, but i thought of the time..
Isn't there any possibility that this can take too long?
I don't know, I'm just predicting!

Yes, there is only the plus operation. Nothing else.
I 've never heard of the knapsack problem before, I think I have to read about it.. Thanks a lot :)

[Yves M]

Yeah this is already too big for brute-force, since 2^1000 is quite a large problem space. So check out some of the solutions given in the link above.

[StreamKid]

I read about the knapsack problem, and of course about the subset sum problem. I'm studing the algos in depth now.
I saw on usenet someone used also the shellsort algo in solving an equal problem. I don't think it's necessary, but I 'll see if it makes things easier.
In anyway, I understood how to correctly solve the problem :)
When ready, I 'll post the code here in case someone after me needs it :)
Thanks in advance, StreamKid

---------------------------------------
Edit
Almost implemented the solution..
But, designed without an important thing.
On the output, you have to print the original position where the number was, and not what numbers you 've used. I find this kinda difficult, since the array is being sorted later on the programm.
Have to overcome this, and then I 'll post the code. :)

[DragForce]

If you need an optimal solution you basically have only two practical options: use branch and bound algorithm or dynamic programming.