Sorting out iterations

[tometherton]

OK I'll try to explain what I'm trying to do...

I've got 16 numbers in an array and I want to find out the best way of adding any combination of these (it can be 2 of them, 5 of them or all of them) to get as close to a possible value as possible.

For example, I want to get to 1000 as my value - I could do this by adding 500 + 700 = 1200 or by adding 300 + 300 + 450 = 1050. Clearly the 1050 is closer but uses 3 values - this doesn't matter but I can only figure out how to add the numbers in order (e.g. value1+value2+value3...+value15+value16) I can't work out how it would take value1+value3+value15 over just value1+value2.

Any thoughts out there or am I trying to do something too clever?!

[Fbody]

Do you have to consider values that are less-than the "target" value as well, or just values that are greater-than-or-equal-to the "target"?

Are the array values randomly-generated, or are they pre-determined values as part of the program specification?

Are there max/min legal values for the "target" value?

[arkoenig]

The problem you are trying to solve is a variation of the Knapsack Problem. There is no exact, general, efficient solution to this problem.

[tometherton]

Do you have to consider values that are less-than the "target" value as well, or just values that are greater-than-or-equal-to the "target"?

I only want to use values that are greater-than-or-equal-to the target value.

Are the array values randomly-generated, or are they pre-determined values as part of the program specification?

The array values would be input by the user and then read from the boxes by the program (though this isn't programmed in yet since the actual front-end isn't designed yet).

Are there max/min legal values for the "target" value?

There is no max/min legal values and the target value would, again, be input by the user (to fit what they are "aiming" for) but again this is not implemented yet - waiting on frotn-end.

@arkoenig Thanks for that I have taken a look at that and rather thought there might not be a simple solution to the problem!!!

T

[Lerner]

>>I can't work out how it would take value1+value3+value15 over just value1+value2.

That should be doable by using two variables of type long to keep track of the closest value yet and the difference between the best yet and the target and a third variable that is an array of 16 ints to keep track of the combination of input values that generated the closest value yet, by either the actual values in the input array of values or the indexes of the array elements representing the input values. Each time you generate a new sum of imputs compare calculate the difference between current sum of inputs and the target and if that difference is smaller than best difference so far, then replace the best so far values with the current values and update the array representing the best combination so far.

[tometherton]

OK I understand how that would work with comparing them - thanks. Is there an 'simple' way to write out the iterations? It is clearly easy to write loops to do 1+2+3...+16, 2+3+4...+16 etc. and then relatively simple to start off with a 'jump' so 1+3+4...+16, 2+4+5...+16 but would it then require a new loop again to do 1+3+5+6...+16 repeating for each time you changed the jump? So you would end up with a lot of separate loops which seems an unelegant solution but probably the only one available...