stould's blog

How to get the path in recursion.
By stould, 11 years ago, In English

Hello, i'm traying a long time to get path of a recursion using DP for the Equipment replacement problem.

N = years to produce M = maximum years machine life P = cost of a new machine V = price to sell the machine on year 'i' CM = price to keep machine on year 'i'

int func(int machine_age, int years_working){
    if(years_working == N){
        return 0;
    }else{
        if(dp[machine_age][years_working] != -1){
            return dp[machine_age][years_working];
        }else{
            if(machine_age > M){
                dp[machine_age][years_working] = P — V[machine_age] + CM[0] + func(1, years_working+1);
                path[years_working] = 1;
            }else{
                int try_keep = CM[machine_age] + func(machine_age+1, years_working+1);
                int try_replace = P — V[machine_age] + CM[0] + func(1, years_working+1);
                if(try_replace <= try_keep){
                    path[years_working] = 1;
                }else{
                    path[years_working] = 0;
                }
                dp[machine_age][years_working] = min(try_keep, try_replace);
            }
        }
        return dp[machine_age][years_working];
    }
}

I'm using a strategy based on: if(keep){ save with 0} else{save with 1}

Can someone help-me to get the path of better decisions to minimize costs of production ?

Thanks a lot.

Tags dp
  • Vote: I like it
  • -15
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

what?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hahahahh Sorry for the inconvenience.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have no idea what you're asking. In general to get the path you just remember somehow which state was the best from this state or how you came to this state or whatever. What you need to know is how you travel (obviously) so if you're minimizing something you say something like "ok i know what the minimum of this subproblem is, but not only that i even know its path (you dont need to care how). Now to know the solution of my problem i just need to append a single path 'vertex' to that subsolution to get the whole path. Ok the general case is solved, the only thing that's left is to take care of the special cases and thats it". I have a feeling you don't understand recursion that well so i'd suggest you work on that first, once you get it, you should be able to come up with what you want on your own

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just insert this code between the 20 and 21st lines: ans++;

→ Reply