Dynamic programming solution for buying a new machine

1. 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.

import java.util.*;

/**
 * Created by IntelliJ IDEA.
 * User: uchan
 * Date: 5/7/12
 * Time: 1:41 PM
 * To change this template use File | Settings | File Templates.
 */
public class OptimalMachineUsage {
    
    private static int initialMachineValue = 100000;
    private static int[] yearlyCost = new int[]{0,6000,8000,12000}; 
    private static int[] valueAfterYear = new int[]{100000,80000,60000,50000};
    
    public static void main(String[] args) {

        Map<String, Integer> possibleSolutions = new LinkedHashMap<String, Integer>();
        findCost(0, 1, 5, 0, new StringBuilder("buy at 0"), possibleSolutions);
        findCost(0, 2, 5, 0, new StringBuilder("buy at 0"), possibleSolutions);
        findCost(0, 3, 5, 0, new StringBuilder("buy at 0"), possibleSolutions);

        int lowCost = Integer.MAX_VALUE;

        List<String> lowCostPaths = new ArrayList<String>();

        for (String path : possibleSolutions.keySet()) {
            System.out.println("(" + path + ") ==> " + possibleSolutions.get(path));
            if(lowCost > possibleSolutions.get(path)) {
                lowCost = possibleSolutions.get(path);
                lowCostPaths.clear();
                lowCostPaths.add(path);
            } else if(lowCost == possibleSolutions.get(path)){
                lowCostPaths.add(path);
            }
        }

        System.out.println("\nLow Cost Paths are ");
        for (String lowCostPath : lowCostPaths) {
            System.out.println(lowCostPath);
        }
        System.out.println("Low Cost Value " + lowCost);

    }
    
    private static void findCost(int buyingYear, int sellingYear, int lastYear, int cost, StringBuilder path, Map<String, Integer> possibleSolutions){
        int operatingCost = findOperatingCost(buyingYear, sellingYear);
        int depreciationCost = findDepreciationCost(buyingYear, sellingYear);


        int costSoFar = cost + (operatingCost + depreciationCost);

        if(sellingYear == lastYear){
            path.append("/sell at " + sellingYear);
            possibleSolutions.put(path.toString(), cost + operatingCost + depreciationCost);
            return ;
        }  else if(sellingYear > lastYear){
            return;
        }

        path.append("/sell and buy at "+ sellingYear);

        findCost(sellingYear, sellingYear+1, lastYear, costSoFar, new StringBuilder(path.toString()), possibleSolutions);
        findCost(sellingYear, sellingYear+2, lastYear, costSoFar, new StringBuilder(path.toString()), possibleSolutions);
        findCost(sellingYear, sellingYear+3, lastYear, costSoFar, new StringBuilder(path.toString()), possibleSolutions);

    }

    private static int findOperatingCost(int buyingYear, int sellingYear) {
        int cost = 0;
        int usage = sellingYear - buyingYear;
        for(int i = 1; i <= usage; i++){
            cost += yearlyCost[i];
        }
        return cost;
    }

    private static int findDepreciationCost(int buyingYear, int sellingYear){
        int usage = sellingYear - buyingYear;
        return initialMachineValue - valueAfterYear[usage];
    }

}

(buy at 0/sell and buy at 1/sell and buy at 2/sell and buy at 3/sell and buy at 4/sell at 5) ==> 130000
(buy at 0/sell and buy at 1/sell and buy at 2/sell and buy at 3/sell at 5) ==> 132000
(buy at 0/sell and buy at 1/sell and buy at 2/sell and buy at 4/sell at 5) ==> 132000
(buy at 0/sell and buy at 1/sell and buy at 2/sell at 5) ==> 128000
(buy at 0/sell and buy at 1/sell and buy at 3/sell and buy at 4/sell at 5) ==> 132000
(buy at 0/sell and buy at 1/sell and buy at 3/sell at 5) ==> 134000
(buy at 0/sell and buy at 1/sell and buy at 4/sell at 5) ==> 128000
(buy at 0/sell and buy at 2/sell and buy at 3/sell and buy at 4/sell at 5) ==> 132000
(buy at 0/sell and buy at 2/sell and buy at 3/sell at 5) ==> 134000
(buy at 0/sell and buy at 2/sell and buy at 4/sell at 5) ==> 134000
(buy at 0/sell and buy at 2/sell at 5) ==> 130000
(buy at 0/sell and buy at 3/sell and buy at 4/sell at 5) ==> 128000
(buy at 0/sell and buy at 3/sell at 5) ==> 130000

Low Cost Paths are
buy at 0/sell and buy at 1/sell and buy at 2/sell at 5
buy at 0/sell and buy at 1/sell and buy at 4/sell at 5
buy at 0/sell and buy at 3/sell and buy at 4/sell at 5
Low Cost Value 128000

Coin problem with greedy approach

import java.util.*;

/**
 * Created by IntelliJ IDEA.
 * User: uchan
 * Date: 5/6/12
 * Time: 9:41 PM
 * To change this template use File | Settings | File Templates.
 */
public class CoinCalc {

    private static int[] coinArray = new int[]{100, 50, 10, 5, 2, 1};

    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println("Please give the amount as an argument");
            return;
        }
        try {
            int amount = Integer.parseInt(args[0]);
            Map<integer, integer> coinSelectionMap = getCoins(amount);
            System.out.println("CoinSelection = " +  coinSelectionMap);
        } catch (NumberFormatException e) {
            System.err.println("Please specify amount as an integer");
        }
    }

    private static Map<integer, integer> getCoins(int amount) {
        Map<integer, integer> coinSelection = new LinkedHashMap<integer, integer>();
        int rest = amount;

        for (int coinValue : coinArray) {
            int numberOfCoins = rest / coinValue;

            if (numberOfCoins == 0) {
                continue;
            }
            rest = rest % coinValue;
            coinSelection.put(coinValue, numberOfCoins);

            if (rest == 0) {
                break;
            }
        }
        return coinSelection;
    }
}