Brute force will work here, since there are only 4 variables. So 3 loops. Loop for x2, x3 and x4 values within limits. Total calculations are 500*333*250, small enough to complete within 5 seconds.
Of course the better approach is DP. On 2/12/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > > Thanks! Solved it now. > > On Feb 12, 4:20 am, "Lego Haryanto" <[EMAIL PROTECTED]> wrote: > > Can be solved by dynamic programming. It can scale also even when we > expand > > this and introduce the 5, 6, or more coefficients. > > > > Think of small stuff first. We know immediately the solution of x1 = n > has > > only 1 solution. > > > > We also know that the solution of 2x2 + x1 = n will have floor(n/2) + 1 > > solution (basically, trying x2 = [0,1,...floor(n/2)] ... and whatever > left > > of this can be solved in 1 way (see the x1 = n solution above). > > > > It's easy to have the solution for 2x2 + x1 = n available and let's > assume > > that we have this in ways[0..n-1] array. > > > > For number of solution for 3x3 + 2x2 + x1 = n, start with trying x3 = 0, > 1, > > ... floor(n/3). For x3 = 0, we have ways[n] solution, for x3 = 1, we > have > > ways[n-3] solution ... etc. > > > > Same rule applies to 4x4. > > > > For this, I'd prefer top down with memoization method rather than bottom > up > > as explained above. > > > > On 2/11/07, Jair Cazarin <[EMAIL PROTECTED]> wrote: > > > > > > > > > I think that a simple backtracking approach could solve this problem. > > > > > On 2/11/07, [EMAIL PROTECTED] < [EMAIL PROTECTED]> wrote: > > > > > > I`m trying to solvehttp://acm.mipt.ru/judge/problems.pl?problem=201. > > > > I`ve tried googling but couldn`t get any way to approach the > problem. > > > > Brute force is ruled out, so how can we solve this problem? > > > > > >http://slipvayne.googlepages.com > > > > -- > > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
