My brute force solution is too slow, needed DP solution

Question

Concise problem definition:

given n and {a,b,c}; 
(1 ≤ n, a, b, c ≤ 4000);
Constraint -> a*i + b*j + c*k==n (i,j,k>=0);
Objective-> maximize(i,j,k)

Examples:

n=47 and a=7,b=5,c=8 -> max=9 (i=1,j=8,k=0) == 7*1+5*8+8*0=47
n=7 and a=5,b=5,c=2  -> max=2 (i=1,j=0,k=1) or (i=0,j=1,k=1) 

My first solution is just brute force and it gives "TIME_LIMIT_EXCEEDED" for some inputs like {4000 and 1,2,3}. I guess this problem can be solved using DP, but I cannot figure it out. I would be very grateful if somebody provide the way how to construct DP solution from this problem. (The main thing I want is not merely solution but I want a good understanding how to build DP solutions). Below is my solution:

#include <iostream>
using namespace std;

int main() {
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    int max=0;

    for (int i=0;i<=n/a;i++) { 
        for (int j=0;j<=n/b;j++) { 
            for (int k=0;k<=n/c;k++) { 

                if ((a*i+b*j+c*k)==n) {
                    if (max<i+j+k) {
                        max = i+j+k;
                    }
                }

            }
        }
    }
    cout<<max;
    return 0;
}

Answer 1

Take the third loop: It is absolutely unneccessary. You check whether (a*i+b*j+c*k)==n. That means k must be equal to (n - a*i - b*j) / c. So a trivial change is to just calculate this one k and check whether it is a solution.

Sort a, b, c such that a ≥ b ≥ c. Now its obvious that as j grows, k must shrink as much or more, so the sum j + k cannot grow. That means if you find a value for k given i and j, you need not bother checking any larger j. The sum i + j + k will not get any larger.

Next I'd look at Euclids algorithm to find solutions of bj + ck = n - ai. And at last, you can estimate how large i + j + k might become as i gets larger. Again, the sum will get tend to get less if i gets larger, and when i is large enough you'll be able to prove that the sum can't get larger anymore.

Answer 2

I guess in the case the 'set of smaller problems' will be :

• maximise(i,j,k) for n - x where x is some number which is harder to compute

So. off the top of my head, I would calculate:

n mod a, n mod b, n mod c

giving me a set of x for which I can easily maximise the corrosponding i,j or k ie.

(n - (n mod a) )/i etc.

and store them along with the remainder, x in a tree structure

Then for each result calculate:

(n mod a) mod b, (n mod a) mod c etc

again storing the remainder and whole fraction in tree nodes underneath the first result.

Once we have reached the end of each path, you can then loop through the tree to calculate the maximised result for n, effectively summing max(n-x) + max(x)

Ie for n = 13, a = 2, b = 3

13 mod 2 = 6 remainder 1
    1 mod 3 = no solution
13 mod 3 = 9 remainder 4
    4 mod 2 = 2 remainder 0

i = 3, j = 2

Answer 3

The OP remarked in a comment that he found the problem tagged as "brute force and DP". Which is absolutely ridiculous. Here's the linear time solution:

1. Observe that the order of a, b, c is quite irrelevant, so sort them to make a ≥ b ≥ c.

2. Calculate g = gcd (a, b, c) (greatest common divisor). If n is not divisible by g then there is no solution. Otherwise, divide a, b, c and n by g. Now gcd (a, b, c) = 1.

3. Calculate g = gcd (b, c), which means n - ai must be a multiple of g. Find i0 = the smallest i such that n - ai is a multiple of g. Such an i exists because gcd (a, g) = 1. Possible values for i that can lead to solutions are i0, i0 + g, i0 + 2g and so on. If n - a*i0 < 0 then there is no solution.

4. Divide b and c by g. We now have to find j, k that solve (n - ai)/g = bj + ck, for i = i0, i0 + g, i0 + 2g and so on. gcd (b, c) is now 1. For each of those i, let m = (n - ai) / g, then we need bj modulo c = m modulo c. Since gcd (b, c) = 1, there is a smallest j0 ≥ 0 solving this equation. The other values j solving this would be j0 + c, j0 + 2c, j + 3c. However, every time we increase j by c we need to decrease k by b, and since b ≥ c this cannot improve the solution. We have k = (m - b * j0) / c, and this k must be ≥ 0. Increasing j cannot make k ≥ 0 if it was less than 0 for a smaller j. This means that for a given i, we choose j = smallest j such that bj modulo c = m modulo c, and k = (m - b * j0) / c.

5. To find j0 quickly, we create a lookup table T mapping a modulo value m to the smallest j with bj modulo c = m. This is done in linear time by calculating b*0 modulo c, b*1 modulo c etc. and setting T [b*t modulo c] = t for 0 ≤ t < c.

6. The algorithm now starts with i = i0, and no solution found so far. If n - ai < 0 then return with the best solution found so far. Otherwise let m = (n - ai) / g. Let j = T [m modulo c], k = (m - b*j) / c. If k ≥ 0 and i + j + k is better than the best solution so far then we found a new best solution. Otherwise continue with i replaced with i + g.

7. We speed up the algorithm by observing that after calculating m, we know that i + j + k ≤ i + m / c which is never increasing. So if we found a solution and i + m / c is not greater than that solution then we can exit the algorithm because we know we found a solution that cannot be improved any further.

With the input n = 4000, a, b, c = 1, 2, 3: We rearrange a = 3, b = 2, c = 1. gcd (a, b, c) = 1 so a, b, c, n remain unchanged. g = gcd (b, c) = 1, so b, c are unchanged, the table T contains one value T [0] = 0.

We let i = 0, and n - ai is divisible by g = 1. So we start with i = 0, m = 4000, j = T [0] = 0, k = (4000 - j*b) / c = 4000, giving the solution i=0,j=0,k=4000.

Next we let i = 1, m = 3997. i + m / c = 3998 < 4000, so the solution that we found earlier is optimal. So the problem that exceeded the time limit is actually so simple that I can write down the complete calculation. (BTW if c = 1 after dividing a, b, c, n by gcd (a, b, c), then i = 0, j = 0, k = n, is always the optimal solution).

I think the solution might be sub-linear in time if we find i0 faster O (g) by using Euclid's algorithm, and instead of building a table T in O (c) find the values j using Euclid's algorithm, hoping that we can prove that quickly that a solution found is optimal.

Answer 4

For recursion, you can redefine your initial problem f (n,a,b,c ) where ai+bj+ck=n to f (n,a,b,c) = ai + f (n-ai,b,c) where f (n,a) becomes finding divisors of n. I can add more detail if you are interested. Answering on mobile is a challenge.

Answer 5

To answer your "DP" question: this can be done in three steps:

1. Find the solutions for a*i==m, where 1<=m<=n: this is simple, just check if m%a==0, then the solution is i=m/a. If not, then there is no solution. Store these in an array.

2. Find the solutions for a*i + b*j==m where 1<=m<=n, maximizing (i+j): loop over all j with 1<=j<=m/b, solve a*i == m-b*j using the results of step 1. For each m, keep the pair (i,j) which has the maximal sum. If you need only the sums as a result, it will be sufficient to keep the sum (i+j) in an array.

3. Finally, solve a*i + b*j + c*k==n by looping over all k and using step 2 to get the solution to a*i + b*j == n - c*k; maximize(i+j). Keep the triple (i,j,k) with maximum sum.