Chocolate-Rain/Rod Cutting.java at master · aky91/Chocolate-Rain · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

class RodCutting {

	//Rod Cutting DP Bottom Up & Top Down with 2D array

	public static Scanner scn = new Scanner(System.in);

	public static void main (String[] args) throws java.lang.Exception{

		int N = scn.nextInt();

		int[] price = new int[N+1];
		HashMap<Integer, Integer> dp = new HashMap<>();
		HashMap<Integer, Integer> choices = new HashMap<>();

		for(int i = 1; i <= N; i++)
			price[i] = scn.nextInt();

		int rodLength = scn.nextInt();

		if(rodLength > N){
			System.out.println("Invalid Input");
			return;
		}

		////////// TOP DOWN

		System.out.println("TOP DOWN");

		System.out.println("max profit : " + getMaxProfitTD(rodLength, price, dp, choices));

		//printing length of pieces

		System.out.print("Pieces : ");

		for(int i = rodLength; i > 0;){

			System.out.print(choices.get(i) + " ");
			i = i - choices.get(i);
		}

		System.out.println("\n");

		////////// BOTTOM UP

		System.out.println("BOTTOM UP");

		System.out.println("max profit : " + getMaxProfitBU(rodLength, price));

	}

	public static int getMaxProfitTD(int rod, int[] price, HashMap<Integer, Integer> dp, HashMap<Integer, Integer> choices){

		if(rod < 0)
			return Integer.MIN_VALUE;

		if(rod == 0)
			return 0;

		if(dp.containsKey(rod))
			return dp.get(rod);

		int ans = Integer.MIN_VALUE;

		for(int cut = 1; cut <= rod; cut++){

			int profit = price[cut] + getMaxProfitTD(rod - cut, price, dp, choices);

			if(profit > ans){
				ans = profit;
				choices.put(rod, cut);
			}
		}

		dp.put(rod, ans);
		return ans;
	}

	public static int getMaxProfitBU(int rodLength, int[] price){

		int[] choices = new int[rodLength + 1];
		int[] ans = new int[rodLength + 1];
		ans[0] = 0;

		for(int rod = 1; rod <= rodLength; rod++){

			int maxProfit = Integer.MIN_VALUE;

			for(int cut = 1; cut <= rod; cut++){

				int profit = price[cut] + ans[rod - cut];
				//maxProfit = Math.max(profit, maxProfit);

				if(profit > maxProfit){
					maxProfit = profit;
					choices[rod] = cut;
				}
			}

			ans[rod] = maxProfit;
		}

		//printing length of pieces

		System.out.print("Pieces : ");

		for(int i = rodLength; i > 0;){

			System.out.print(choices[i] + " ");
			i = i - choices[i];
		}

		System.out.println();

		return ans[rodLength];
	}

}