Optimization problem where penalty is sensitive to permutation

Question

Say, I have the situation where I am looking into all the possibilities to obtain a value of e.g. 20 (exactly) by taking all possible combinations of sums using values from 1 to 5. While doing this, I want to minimize my penalty P. There is no limit to the amount of values I use (I could do 4x5, 20x1 and any other possibility).

The penalty is not based on the amount of values I use, but instead on the intermediate values of the summation.

In this example, let's assume the penalties are as follows:

• 1 * k for 0 <= S < 2
• 2 * k for 2 <= S < 6
• 3 * k for 6 <= S < 11
• 4 * k for 11 <= S < 20

where k is the current value being added to my intermediate sum S.

So if I consider e.g. [1,2,3,4,5,5] (in that particular order), my total penalty would be P=1*1+1*2+2*3+3*4+3*5+4*5=56.

However, the penalty changes if I permute my array to e.g. [1,5,4,5,2,3] (P=53) or [2,4,5,1,3,5] (P=61).

In this simple example, we have 192 different sets of values that can together add up to 20. The number of possible permutations per set (taking into account non-unique values) varies between 1 (in case of 20x1, 10x2 etc) and 15840 (7x1, 3x2, 1x3, 1x4). The naive approach would be to just loop through all sets and their permutations, which is doable for the given example.

However, my actual problem has about 2000 possible sets of numbers and the number of permutations goes all the way up to ~1E+8. It is no longer fun to use a naive approach in this case.

I do know that I can greatly reduce my number of permutations, as the order of my values does not matter if I stay within the same range (when I'm at S=11, it no longer matters in what way I add the final 9).

My question is how I can properly implement this knowledge to improve my naive algorithm such that it disregards those permutations a priori (first generating all permutations and then removing is not really an option, as even 8-bit unsigned integers will generate 15 GB arrays for all permutations). Furthermore, I was wondering whether there are any additional improvements that could be made here.