Minimum Cost Algorithm

[crazymidget01]

I have a project where we are calculating the cost of shipping a product from manufacturer to warehouse using North-west corner and also using another method to find the minimum cost to meet the demand. I am stuck on coding the minimum cost algorithm, I understand the minimum cost algorithm, but can not figure out how to implement it. You must find the lowest cost in a 2-d array, ship as much of the supply as you can per demand, then find next lowest cost and do the same until demand is met. I am sure there is an easier way to do this than how I was trying to do it. I appreciate any help anyone can provide!

Thanks

public class NWcorner2 {
    public static void main(String[] args)
    {
        int[] s = {100, 200, 300};   // Supply
        int[] d = {150, 350, 100};   // Demand
        int[][] c = { {11, 12, 14},  // Cost per item from source (row) to 
                      { 9, 19, 10},  //     destination (column)
                      {25, 12, 17}};
        NorthWest(s,d,c);            // Calculate Shipping using NW Corner
        MinCost(s,d,c);              // Calculate Shipping using min cost method
        //percentSaved(NorthWest(s,d,c),MinCost(s,d,c));
    }
    
    public static int NorthWest(int[] s, int[] d, int[][] c){
    int[][] table = new int[s.length][d.length];
    int[]supply = s.clone();        // copy supply and demand array so original
    int[]demand = d.clone();        // arrays remain unchanged
    int totalCost = 0;
    
        for(int i=0; i < supply.length; i++)
        {
            for(int j=0; j < demand.length; j++)
            {
                // If Supply >= Demand, demand is filled completely, demand = 0
                if(supply[i] >= demand[j])        
                {
                    table[i][j] = demand[j];
                    supply[i] = supply[i] - demand[j];
                    demand[j] = 0;
                }
                // If Supply < Demand, demand = demand - supply, supply = 0
                else
                {
                    table[i][j] = supply[i];
                    demand[j]= demand[j] - supply[i];
                    supply[i] = 0;
                }
                System.out.print(table[i][j] + "\t");   // Print as calculated
            }
            System.out.println();                       // New line
        }
        // Calculate Shipping cost using NW Corner method
        for(int i=0; i<=2; i++)
        {
            for(int j=0; j<=2;j++)
            {
                totalCost = totalCost + c[i][j]*table[i][j];
            }
        }
        System.out.println("Total Cost = $" + totalCost);
        return(totalCost);
    }
    
    
    
    public static int MinCost(int[] s, int[] d, int[][] c){
        int[][] table = new int[s.length][d.length];
        int[]supply = s.clone();        // copy supply and demand and cost array 
        int[]demand = d.clone();        // so original arrays remain unchanged
        int[][]cost = c.clone();
        int totalCost = 0;
        int smallest = c[0][0];
        int ii=0, jj=0;
        boolean rowSatisfied = false;
        boolean colSatisfied = false;
    
        // find smallest cost of shipment from supplier
        for(int i=0; i < supply.length; i++)
        {
          for(int j=0; j < demand.length; j++)
          {
                if(smallest > cost[i][j])
                {
                  smallest = cost[i][j];
                  ii=i;
                    jj=j;
                }
          }
        }
        int last = smallest;
    
        while(colSatisfied != true)
        {
            // If Supply >= Demand, demand is filled completely, demand = 0
            if(supply[ii] >= demand[jj])
            {
                table[ii][jj] = demand[jj];
                supply[ii] = supply[ii] - demand[jj];
                demand[jj] = 0;
            }
            // If Supply < Demand, demand = demand - supply, supply = 0
            else{
                table[ii][jj] = supply[ii];
                demand[jj]= demand[jj] - supply[ii];
                supply[ii] = 0;
            }
            System.out.println("table " + table[ii][jj]);
            System.out.println(ii + "  " + jj);
        
            System.out.println("supply " + supply[ii]);
            System.out.println("demand " + demand[jj]);
            System.out.println("smallest " + smallest + " last " + last);
            int temp = 0;

            // Find next smallest cost of shipping
            for(int i=0;i<s.length;i++)
            {
                if(cost[i][jj] > last)
                {
                    temp = cost[i][jj];
                    System.out.println(temp);
                    if(temp <= cost[i][jj])
                    {
                        smallest = cost[i][jj];
                        ii=i;
                        System.out.println(i +" "+ temp);
                    }
                }System.out.println(i + " " + ii + "  " + jj + " " + smallest);
            } System.out.println("smallest " + smallest + " last " + last);


            System.out.println(ii + "  " + jj);
            if(demand[jj] == 0)
                colSatisfied = true;
        }
         
     // Calculate Shipping cost using Minimum Cost Method
     for(int i=0; i<=2; i++){
        for(int j=0; j<=2;j++){
            totalCost = totalCost + c[i][j]*table[i][j]; 
        }
     }
     System.out.println("Total Cost = $" + totalCost);
     return(totalCost);
    }

    // Calculate percentage saved using minPrice method over NWcorner method
    public static void percentSaved(int NWprice, int minPrice){
        System.out.println("Percentage "
                + "saved: "+ (100-(minPrice/NWprice)*100) + "%");
        
    }
}

[NormR1]

Sounds like an algorithm/logic problem. If you have the algorithm, and have specific questions about how to implement it in java, please post your questions.

Can you list the steps in solving the problem and where you are having the problem.

[crazymidget01]

Using a two dimensional array where rows correspond to a manufacturer and columns correspond to a warehouse. Each cell contains the price of shipping from certain manufacturer to a certain warehouse. The algorithm for finding the lowest cost of shipping using constraints of supply and demand array:

1. Identify the cell having minimum unit transportation cost (cij).
2. Choose the value of the corresponding xij
as much as possible subject to the
capacity and requirement constraints.
3. If demand is satisfied, delete the column .
4. If supply is exhausted, delete the row.
5. Repeat steps 1-4 until all restrictions are satisfied

My question is how to implement this. Can you delete a row or column in a 2-d array, or should new arrays be created after each row or column is satisfied? Or is there a better way to go about this problem?

Thanks again

[dantinkakkar]

No, you can delete it, though there is no quick function for doing this, I guess. You can just shift the values of the rows on top of it to that row.

For example, if your array is this:

X X X X X
Y Y Y Y Y
Z Z Z Z Z
N N N N N

To delete the, say, second row, that is Y Y Y Y Y, just move the rows below it by one.

[crazymidget01]

Had another idea, how about multiplying row or column to be deleted by a large number? Essentially deleting it...or excluding it so on the next pass of looking for the next cheapest shipping cost neglects the row/column.

public class NWcorner2 {
    static int ii, jj;
    
    public static void main(String[] args)
    {
        int[] s = {100, 200, 300};   // Supply
        int[] d = {150, 350, 100};   // Demand
        int[][] c = { {11, 12, 14},  // Cost per item from source (row) to 
                      { 9, 19, 10},  //     destination (column)
                      {25, 12, 17}};
        //NorthWest(s,d,c);            // Calculate Shipping using NW Corner
        MinCost(s,d,c);              // Calculate Shipping using min cost method
        //percentSaved(NorthWest(s,d,c),MinCost(s,d,c));
    }
    
    public static int MinCost(int[] s, int[] d, int[][] c){
        int[][] table = new int[s.length][d.length];
        int[]supply = s.clone();        // copy supply and demand and cost array 
        int[]demand = d.clone();        // so original arrays remain unchanged
        int[][]cost = c.clone();
        int x=0;
        int w = 0;
        int totalCost = 0;
        boolean done = false;
        
        System.out.println(ii + "   " + jj);
        printcost(cost);
            
        while (!done)
        {
            // find smallest cost of shipment from supplier
            x = cheapest(cost, supply.length, demand.length);
                
            System.out.println(x + "   " + ii + "   " + jj);
                // If Supply >= Demand, demand is filled completely, demand = 0
                if(supply[ii] >= demand[jj])        
                {
                    table[ii][jj] = demand[jj];
                    supply[ii] = supply[ii] - demand[jj];
                    demand[jj] = 0;
                    // Multiply column by 10000, essentially deleting it when
                    // finding next smallest value
                    for(int i=0; i<demand.length;i++){
                        cost[i][jj] = cost[i][jj]*10000;
                    }
                    printcost(cost);
                }
                // If Supply < Demand, demand = demand - supply, supply = 0
                    else
                    {
                        table[ii][jj] = supply[ii];
                        demand[jj]= demand[jj] - supply[ii];
                        supply[ii] = 0;
                        // Delete row
                        for(int i=0; i<supply.length;i++){
                            cost[ii][i] = cost[ii][i]*10000;
                        }
                    }printcost(cost);
                    System.out.print(table[ii][jj] + "\t");   // Print as calculated

                System.out.println();                       // New line
                w++;
                if(w == 4){
                done = true;}
       }
     // Calculate Shipping cost using Minimum Cost Method
     for(int i=0; i<=2; i++){
        for(int j=0; j<=2;j++){
            totalCost = totalCost + c[i][j]*table[i][j]; 
        }
     }
     System.out.println("Total Cost = $" + totalCost);
     return(totalCost);
    }

    // Calculate percentage saved using minPrice method over NWcorner method
    public static void percentSaved(int NWprice, int minPrice){
        System.out.println("Percentage "
                + "saved: "+ (100-(minPrice/NWprice)*100) + "%");
        
    }
    
    public static int cheapest(int[][] cost, int row, int col){
    
        int smallest = cost[0][0];
    
        for(int i=0; i < row; i++)
        {
          for(int j=0; j < col; j++)
          {
                if(smallest > cost[i][j])
                {
                  smallest = cost[i][j];
                  ii=i;
                  jj=j;
                }
          }
        }
        return smallest;
    }
    
    public static void printcost(int[][] cost)
    {
        for(int i=0;i<cost.length;i++){
            for(int j=0; j<cost.length; j++){
                System.out.print(cost[i][j] + "\t");
            }System.out.println("");
        }
    }
}

[dantinkakkar]

Won't that be very data-consuming? OR if you are going through the same array again and again, at the point where you wanna delete a row/column, copy out that array EXCEPT that row/column into another array, and then re-initialize your old array, and copy back the values into it. That way, you can use the same two arrays and get your work done easily.

[ejosiah]

How about using an ArrayList and have the power of Java Collection API at your finger tips

[ejosiah]

java.util.Collections is got alot of methods and its also got max and min methods which can save you alot of lines of code; check it out