3
$\begingroup$

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.

Number of permutations as function of set number

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.

$\endgroup$
  • 3
    $\begingroup$ That sounds like a fun exercise / problem! Where did you run across it? What's the context in which you encountered this? Anyway, what algorithm design paradigms have you tried so far? Have you tried dynamic programming? Looks like this should be solvable straightforwardly using dynamic programming (check out the link). $\endgroup$ – D.W. Mar 2 '17 at 19:45
  • $\begingroup$ @D.W. It actually originates from the upgrade system in a game, where the cost of a full upgrade is determined partly by what I described (in currency A) and partly by something independent of the order one performs the upgrades in (but depending on quantity, paid in currency B). I'm trying to write a dynamic tool where one can specify a weight for the 2 currencies and then find the optimal quantities + order to minimize total cost. I'm not at all familiar with optimization problems, so I have not gone past what I described (i.e. starting naive, then trying to improve). Will check your link! $\endgroup$ – slvrbld Mar 3 '17 at 10:44
2
$\begingroup$

I will outline two different solution methods. Either one will work -- pick whichever one you find easiest to understand and implement.

Dynamic programming

This can be solved using dynamic programming. We'll fill in a one-dimensional table, so that $T[s]$ stores the penalty of the best (lowest-penalty) way to obtain a sum of exactly $s$. Once we've filled in all of the entries, $T[20]$ will tell you the lowest penalty achievable for any combination that sums to 20.

So how do we fill in the table entries? We can fill them in recursively:

$$T[s] = \min(T[s-1]+p(s-1,1), T[s-2]+p(s-2,2), \dots, T[s-5]+p(s-5,5))$$

where $p(s,k)$ is the penalty for adding the number $k$ when the intermediate sum is $s$. In the question, you tell us that $p(s,k) = k$ for $0 \le s < 2$, $p(s,k) = 2k$ for $2 \le s < 6$, etc.

Also, we have the base cases $T[0] = 0$. As a convention, we'll agree that $T[-1]=T[-2]=T[-3]=T[-4]=\infty$. Then you can fill in $T[1],T[2],\dots,T[20]$ in that order, using the recursive formula above.

This will give you the penalty of the best way to achieve the sum $20$. If you also want to output the specific combination that achieves that penalty, you can keep track of that with a small modification. Basically, each time you fill in a $T[i]$ entry with some penalty value, on the side keep track of the combination that led to that penalty value.

Graph search

Construct a weighted directed graph, with vertices 0, 1, 2, .., 20. Each vertex corresponds to a possible intermediate sum. From each vertex (intermediate sum) $s$, add five outgoing edges, corresponding to the five possibilities for the number you add. The length of the edge from $s$ to $s+i$ (for $i=1,2,\dots,5$) is the penalty for adding $i$ to an intermediate sum $s$, according to the rules described in your question.

Now find the shortest path from vertex 0 to vertex 20 in this graph. That path will correspond to a combination of values that sum to 20, and the total length of that path will correspond to the penalty of that path. The shortest path will correspond to the combination with lowest penalty. You can use any standard algorithm for computing shortest paths in a graph, such as Dijkstra's algorithm.

$\endgroup$
  • $\begingroup$ Thanks a lot for giving me a pointer in the right direction. It has become evident to me that a recursive approach is the way to go to solve such a problem. I'm going to do some reading on the two approaches you've outlined and try to do a simple implementation when I find some time for it. Will mark as accepted as soon as I get something working! $\endgroup$ – slvrbld Mar 6 '17 at 9:20
0
$\begingroup$

I'd change it from "penalties" to rewards. Pretend you have n slots that you need to fill with coins, and you have piles with different amounts of coins available. You can take a pile of k coins, find k consecutive empty slots, and fill these slots with coins.

Now the rewards: In your example, if you take a pile of k points and start dropping them at position 0 ≤ S < 2, and S + k > 2, then you get S + k - 2 rewards. If you start dropping them at position 2 ≤ S < 6, and S + k > 6, then you get S + k - 2 rewards and so on.

We can simplify this: If you drop m coins at position S, and S is the highest position 0 ≤ S < 2 where coins are dropped, then you get S + k - 2 rewards. In your example you can get 3 rewards (the fourth reward is always zero), so you maximise the sum of those three rewards.

$\endgroup$
  • $\begingroup$ Can you clarify how the rewards are defined, more generally? I don't quite see the pattern you're trying to get at. Also, how does this lead to an algorithm? Can you be more explicit about what the algorithm is? $\endgroup$ – D.W. Mar 3 '17 at 0:40
1
$\begingroup$

Another way to view the problem using Dynamic Programming might be the following. We can first define the discrete recurrence relation of your sequence to be the following:

\begin{align} s_{n+1} &= s_{n} + u_{n} \end{align}

where $s_{n}$ is the sum up to, but not including, the $n^{th}$ term of the sequence, and $u_{n}$ is the $n^{th}$ sequence term you will choose based on your set of possible sequence term values. Note all the possible values for the variables are as followed (based on your example):

\begin{align} u_{n} &\in \mathcal{U} = \lbrace 1,2,3,4,5\rbrace \;\; \forall n\\ s_{n} &\in \mathcal{S}_{n} =\lbrace k \in \mathbb{N}: (n-1) \leq k \leq 5(n-1) \rbrace \end{align}

The above expression shows the set of possible values for $s_1$ is only $\lbrace 0 \rbrace$, but grows larger each step in the sequence. The possible values for $s_{n}$ can be reduced by tailoring the sets for a sum equal to $20$, but you can figure that out on your own. The next step is to define some cost function we wish to minimize with respect to $\lbrace u_{n} \rbrace_{n=1}^{M}$, perhaps:

\begin{align} V &= \gamma (s_{M+1}-20)^2 + \sum_{n=1}^{M} P_{n}(s_{n},u_{n}) \end{align}

where $M$ is the size of the sequence, $s_{M+1}$ is the final sum across all values chosen in the sequence, $\gamma$ is some constant, and $P_{n}(\cdot,\cdot)$ is some penalty at the $n^{th}$ sequence as a function of the current sum ($s_{n}$) and $n^{th}$ chosen sequence term value ($u_{n}$). We can break this into pieces and recursively solve the optimization by doing the following:

\begin{align} V^{*}_{M+1}(s) &= \gamma (s - 20)^2 \; \forall s \in \mathcal{S}_{M+1} \\ V^{*}_{n}(s) &= \min_{u \in \mathcal{U}} P_{n}(s,u) + V^{*}_{n+1}(s+u) \;\;\forall s \in \mathcal{S}_n\\ u^{*}_{n}(s) &= \arg \min_{u \in \mathcal{U}} P_{n}(s,u) + V^{*}_{n+1}(s+u) \;\; \forall s \in \mathcal{S}_n \end{align}

Since this problem is discrete, you can obtain $V^{*}_{n}(s),u^{*}_{n}(s)$ by just looping through all $u \in \mathcal{U}$ for some $s \in \mathcal{S}_{n}$ and store the best cost and choice values as $V^{*}_{n}(s),u^{*}_{n}(s)$ in lookup-tables/arrays. Once you have computed those optimal values, you can start at $s_1 = 0$ and generate an optimal sequence using the discrete recurrence relation and $u^{*}_{n}(s)$.

Edit 3/5/2017

I implemented a code for the vanilla approach I describe above that you can check out here. Using this code, you can specify the sequence size you're interested in, the range of values that make up $\mathcal{U}$, the function $P_{n}(s_n,u_n)$, and the final cost term (which I define as $\gamma (s - 20)^2$ ). The algorithm technically obtains an optimal policy (that need not be unique) and then uses it to generate the optimal sequence.

Using the example provided by the OP, the code finds a sequence of $( 1, 4, 5, 5, 1, 4 )$ as optimal with a penalty of $P = 50$. If I then increase the sequence size to have 10 elements, the optimal sequence $( 1, 3, 1, 5, 5, 1, 1, 1, 1, 1 )$ comes out with a penalty of $P = 51$. If I increase the sequence size to have 15 elements, the optimal sequence $( 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 1, 1, 1, 1, 1 )$ comes out with a penalty of $P = 56$.

The Dynamic Programming formulation makes these results quite efficient to obtain, though things could be slimmed down further with some clever modifications.

$\endgroup$
  • $\begingroup$ Where did your $V$ come from, and why do we care about its value? The problem already defines a cost function (the sum of the penalties, i.e., $\sum_{n=1}^M P_n(s_n,u_n)$). What is the purpose/motivation of the additional term in $V$? I like the setup, but it seems you are solving a different problem than the one in the question -- it looks to me like you're optimizing a different objective function. For instance, might your algorithm output a sequence that ends at something other than 20? It seems like it might -- do you have a proof that won't happen? $\endgroup$ – D.W. Mar 5 '17 at 11:54
  • $\begingroup$ @D.W. That final term is like a soft constraint to push the found sequence to result in a sum of 20, since I didn't constrain the sets of possible sum values, $\mathcal{S}_n$. Choosing a sufficiently large $\gamma$ will result in the desired optimal sequence, while removing the term could allow an optimal sequence that does not sum to 20 (given that more than one possible sequence can attain the same minimum penalty for $\sum_{n=1}^{M} P_{n}(s_n,u_n)$). $\endgroup$ – spektr Mar 5 '17 at 15:01
  • $\begingroup$ @D.W. I briefly note in my answer, but it is possible to constrain $\mathcal{S}_{n}$ such that the final allowable sum value is only 20, and in that case you could avoid that final term. But I am leaving that for the OP to think about. $\endgroup$ – spektr Mar 5 '17 at 15:01
  • $\begingroup$ Thanks a lot for your example implementation. I'm first going to try my own implementation to get some fundamental understanding of the dynamic programming approach itself and then I'll review your implementation and the reasoning behind it. $\endgroup$ – slvrbld Mar 6 '17 at 9:34
  • 1
    $\begingroup$ @C.Howard I actually overestimated the problem. D.W.'s nudge in the right direction was enough to quickly solve it! I've added my solution as a separate answer. Feel free to have a look and check if there can be made any improvements. $\endgroup$ – slvrbld Mar 6 '17 at 13:16
1
$\begingroup$

With the help of D.W.'s answer I managed to tackle the problem quite easily.

See below code for my implementation of the example problem in MATLAB using dynamic programming. If there's any way to further optimize this, I'd love to hear it!

edit: also added the graph search approach. That one was ridiculously simple to implement..!

Caller script (Dynamic programming)

% Set target value
V = 20;

% Define globals for lookup-table LUT and allowed values pVals
global pVals LUT
pVals   = randperm(5);  % use values 1 to 5 in random order
LUT     = cell(2,V);    % row 1: minimum penalty | row 2: used values

% Perform the calculation
[minPenal, usedVals] = T(V);

% Verify correctness of answer
currPenal = 0;
currSum   = 0;
for ii=1:length(usedVals)
    currPenal = currPenal + p(currSum, usedVals(ii));
    currSum   = currSum + usedVals(ii);
end

if isequal(minPenal, currPenal) && (currSum==V)
    fprintf('\rPossible solution (P = %d):\n%s\n', minPenal, num2str(usedVals))
else
    fprintf('\rSomehow the recursion failed to obtain a solution... :(\n')
end

The recursive function (Dynamic programming)

function [minPenalUpToVal, bestSeq] = T(targetVal)

global pVals LUT

if ~isempty(LUT{1,targetVal})
    % No need to redo the calculation if it has been done already
    minPenalUpToVal = LUT{1,targetVal};
    bestSeq         = LUT{2,targetVal};

else
    % Initialize arrays    
    currPenal   = zeros(1,length(pVals));
    currSeq     = cell(1,length(pVals));

    % Loop over all possibile "previous states" that could result in V
    for pv = 1:length(currPenal)

        % Fetch the increment that may have made the current target possible
        incr = pVals(pv);

        if (targetVal-incr < 0) % Invalid, we rule this out by setting the penalty to inf
            currPenal(pv)  = inf;

        elseif (targetVal-incr == 0) % We know the penalty is zero at zero, so we don't need a minimum penalty
            currPenal(pv)  = 0 + p(targetVal-incr,incr);

        else % Recursive approach to get the minimum penalty up to V along with a possible solution to get there
            [penalUpToVal, currSeq{pv}] = T(targetVal-incr);
            currPenal(pv)               = penalUpToVal + p(targetVal-incr,incr);
        end
    end

    % We are only interested in the lowest penalty to get to V
    [minPenalUpToVal, idx]  = min( currPenal );
    bestSeq                 = [currSeq{idx} pVals(idx)];

    % Store these above quantities in our lookup-table
    LUT{1,targetVal} = minPenalUpToVal;
    LUT{2,targetVal} = bestSeq;

end

end

Caller script (Graph search)

% Set target value
V       = 20;
pVals   = randperm(5);  % use values 1 to 5 in random order

% Preallocate matrix
A = zeros(V+1,V+1);
for ii=1:V+1 % Loop over nodes
    for jj=pVals % Generate the edges
        if (ii+jj <= V+1) % Avoid exceeding our target
            A(ii, ii+jj) = p(ii-1, jj);
        end
    end
end

% Solve the problem with MATLAB built-in functions.
G       = digraph(A);
[sP,dP] = shortestpath(G, 1, V+1);
fprintf('\rPossible solution (P = %d):\n%s\n', dP, num2str(diff(sP)));

Penalty function

function p_out = p(s, k)

if (s < 2)
    p_out = 1*k;

elseif (s < 6)
    p_out = 2*k;

elseif (s < 11)
    p_out = 3*k;

elseif (s < 20)
    p_out = 4*k;

end

end
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.