Help with an algorythm

[Johnny97]

I am wondering if anyone can give me some help or advice.
I am trying to write an algorythm for a personnal project (just fun)
the algorythm goes like this. we have an array of random numbers:
[2, 32, 21, 5, 18, 18, 20, ...]
as you can see, the numbers vary and the size of the array vary. these are random numbers inputed by the user.
they CAN be repeated. in this example, 18 is repeated.

now. I have a maximum amount. let's say 50.
what I want to know is, how can I fit these numbers into 50, with having the least remainder possible.

so, I can have:
18,18,5,2 = 43
or
20,21,5,2 = 48
or
32, 18 = 50

I cannot go over the maximum amount...
I can add as many values as I want, without going over maximum (50 in this case)
in this example, 32,18 is the best since it hits exactly 50.


how would I go testing every combination efficiently? is there a quick way to find the best combination?
ideally, my goal is to repeat this process over and over until there are no numbers left in the array.
so once we find 23 and 18, we remove those and start over. perhaps 20,21,5,2 is the next best combination, we remove those and so on.

not sure how to start with this but wondering if some maths could be used to quickly find the most ideal combination fast?

 

[WhiteCube]

To keep this example simple I will use the numbers [1,2,2,5]

I have 3 different values, so I need 3 arrays. Initialised to non numeric values. The position represents the sum.

A(0)=[?,?,?,?,?,?,?,?,?,?,?]
A(1)=[?,?,?,?,?,?,?,?,?,?,?]
A(2)=[?,?,?,?,?,?,?,?,?,?,?]

I can use 0 or 1 ones.

A(0)(0)=0
A(0)(1)=1

I can use 0, 1 or 2 twos.

FOR i = 0 TO 10
  IF A(0)(i) is numeric
    A(1)(i+0*2)=0
    A(1)(i+1*2)=1
    A(1)(i+2*2)=2

I can use 0 or 1 fives.

FOR i = 0 TO 10
  IF A(1)(i) is numeric
    A(2)(i+0*5)=0
    A(2)(i+1*5)=1

A(0) [0,1,?,?,?,?,?,?,?,?,?]
A(1) [0,0,1,1,2,2,?,?,?,?,?]
A(2) [0,0,0,0,0,0,1,1,1,1,1]

A numeric value in position i of the last array means a sum of i is possible.

To get one possibility, work backwards.

example i = 7

quantity is A(2)(i)
 so, 1 five

i -= 1*5

quantity is A(1)(i)
 so, 1 two

i -= 1*2

quantity is A(0)(i)
 so, 0 ones

result: [5,2]

 

[WhiteCube]

PS

I put the numbers in order, but the method will work in any order.

The arrays could be as short as maximum+1, they don't have to be the total possible sum.

I grouped numbers with the same value together, but it is not necessary.

 

[Johnny97]

no quite sure what you did. bit confused...

but, I actually ended up using the subset-sum problem to create arrays, grouping all the values together.
the last entries in the array are the answer.
if there are no entries, the before last is closest solution and so on.

my algorythm also stops when no more values or if the max value (in my case 50) was found and takes those pairs of numbers and removes from initial set.
then restarts the computation until the original array of number is empty.

 

[WhiteCube]

Sorry about being unclear. I thought going through a small example would be better than pseudocode.

Its a bit hard to swallow.

pseudocode:

set = {2,32,21,5,18,18,20}
maximum = 50
PRINT subset(set,maximum)
END

FUNCTION array(V,Q)
  return an array, length Q, all elements are V

FUNCTION subset(S,M)
N = length(S)
A = array(array(-1,M+1),N)
A[0][0] = 0
IF S[0] <= M
  A[0][S[0]] = 1
FOR I = 1 TO N-1
  FOR J = 0 TO M
    IF A[I-1][J] != -1
      A[I][J] = 0
      IF J+S[I] <= M
        A[I][J+S[I]] = 1
I = M
WHILE A[N-1][I] == -1
  I -= 1
R = an empty array
FOR J = N-1 TO 0 STEP -1
  IF A[J][I] == 1
    append S[J] to R
    I -= S[J]
RETURN R

 

[Johnny97]

Sorry about being unclear. I thought going through a small example would be better than pseudocode.

Its a bit hard to swallow.

pseudocode:

set = {2,32,21,5,18,18,20}
maximum = 50
PRINT subset(set,maximum)
END

FUNCTION array(V,Q)
  return an array, length Q, all elements are V

FUNCTION subset(S,M)
N = length(S)
A = array(array(-1,M+1),N)
A[0][0] = 0
IF S[0] <= M
  A[0][S[0]] = 1
FOR I = 1 TO N-1
  FOR J = 0 TO M
    IF A[I-1][J] != -1
      A[I][J] = 0
      IF J+S[I] <= M
        A[I][J+S[I]] = 1
I = M
WHILE A[N-1][I] == -1
  I -= 1
R = an empty array
FOR J = N-1 TO 0 STEP -1
  IF A[J][I] == 1
    append S[J] to R
    I -= S[J]
RETURN R

its bit hard to follow kuz Im working in javascript. it looks to be python or something.
But i think what I did is working so dont need to bother '