Suppose a company needs to have a machine over the next five year period. Each new machine costs Rs.100,000. The annual cost of operating a machine during its ith year of operation is given as follows: C1 = 6000, C2 = 8000 and C3 = 12,000. A machine may be kept up to three years before being traded in. This means that a machine can be either kept or traded with in the first two years and has to be traded when its age is three. The trade in value after i years is t1= 80,000, t2 = 60,000 and t3 = 50,000. How can the company minimize costs over the five year period (year 0 to year 5) if the company is going to buy a new machine in the year 0?
Devise an optimal solution based on dynamic programming. Illustrate appropriate stages/ states and the optimal-value function.
class test{
public static int i=6;
public static int p=100000;
public static int[] get= new int[i];
public static void main(String args[]){
//get(t)=minimum net cost from time "t" to 5.given that a new vehicle is perchased at time t.
//getr(t) is also the same.
//cs[t][x]= net cost of buying a bycicle at "t" time and operating it until time "x".
//in this programme, we are trying to find get(0).
//value function -> get(t)=min{c[t][x]+g(x)}, t=0,1,2,3,4
int[][] cs = { //0 1 2 3 4 5
/*0*/{0,26000,54000,76000, 0, 0},
/*1*/{0, 0,26000,54000,76000, 0},
/*2*/{0, 0, 0,26000,54000,76000},
/*3*/{0, 0, 0, 0,26000,54000},
/*4*/{0, 0, 0, 0, 0,26000},
/*5*/{0, 0, 0, 0, 0, 0}
};
//initialising arrays
for(int j=0;j<5;j++){
get[j]=-1;
}
get[5]=0;
System.out.println("# Using recursive method without DP ");
System.out.println("=====================================");
System.out.println("below shows the number of calles to getr()");
System.out.println("");
System.out.println("\n"+"Minimum cost is "+getr(0,cs));
System.out.println("");
System.out.println("");
System.out.println("# Using recursive method with DP ");
System.out.println("=====================================");
System.out.println("below shows the number of calles to get()");
System.out.println("");
System.out.println("\n"+"Minimum cost is "+get(0,cs));
System.out.println("");
System.out.println("--------------------------------------------");
System.out.println("# We can use DP to get an optimal solution #");
System.out.println("--------------------------------------------");
System.out.println("");
findpath1(0,cs);
System.out.println("--------------------------------------------");
}
//////////////////////////////////////////////////////////////////////////
// this method calculates the minimum cost without using DP //
/////////////////////////////////////////////////////////////////////////
public static int getr(int c,int[][] x){
System.out.println("call getr["+(c)+"]");
int min=-1;
int tp=0;
//base case
if(c==5) return 0;
//check all the possible values and get the minimum
for(int i=1;i<4;i++){
if((c+i)<6){
if(i==1){
min=x[c][c+i]+getr(c+i,x);
}
else{
tp=(x[c][c+i]+getr(c+i,x));
if( min> tp ){
min=tp;
}
}
}
}
//return the minimum value
return min;
}
//////////////////////////////////////////////////////////////////////////
// this method calculates the minimum cost using DP //
/////////////////////////////////////////////////////////////////////////
public static int get(int c,int[][] x){
System.out.println("call get["+(c)+"]");
int tmp=0;
int min=-1;
//base case
//if(c==5) return get[5];
//check all the possible values and get the minimum
for(int i=1;i<4;i++){
if((c+i)<6){
if(i==1){
//if the item is not in the table. then calculate
if(get[c+i]==-1){
min=x[c][c+i]+get(c+i,x);
}
//if the item is in the table. then get it
else{
min=x[c][c+i]+get[c+i];
}
}else{
//if the item is not in the table. then calculate
if(get[c+i]==-1){
tmp=x[c][c+i]+get(c+i,x);
}
//if the item is in the table. then get it
else{
tmp=x[c][c+i]+get[c+i];
}
//finding the minumum
if( min> tmp ){
min=tmp;
}
}
}
}
//put the minimum value in the table
get[c]=min;
//return the minimum value
return min;
}
//////////////////////////////////////////////////////////////////////////
// this method finds the minimum cost paths //
/////////////////////////////////////////////////////////////////////////
public static void findpath1(int c,int[][] x){
System.out.println("Minimum cost paths if we buy at "+c);
System.out.println("===================================");
//find the paths from time "t", where are the costs are minimum.
for(int i=1;i<4;i++){
if((c+i)<6){
if(x[c][c+i]+get[c+i]==get[c]){
//call findpath method()
findpath(c+i,x);
}
}
}
}
//////////////////////////////////////////////////////////////////////////
// this method finds the minimum cost paths //
/////////////////////////////////////////////////////////////////////////
public static void findpath(int c,int[][] x){
int j=c+1;
if(c>4){
System.out.println("");
}
else{
for(int i=1;i<4;i++){
if((c+i)<6){
if( (x[c][c+i]+get[c+i])==get[c]){
System.out.print("buy--> ["+c+"] sell at ["+(c+i)+"] /");
findpath(c+i,x);
}
}
}
}
}
}
0 comments:
Post a Comment