Merge pull request MukulCode#447 from vipul-027/cp

MukulCode · web-flow · commit d8dc1cb3e7f1 · 2022-10-18T23:46:06.000+05:30
A recursive solution for Rod cutting problem
diff --git a/cpp/Rod_cutting.cpp b/cpp/Rod_cutting.cpp
@@ -0,0 +1,43 @@
+// A recursive solution for Rod cutting problem
+#include <bits/stdc++.h>
+#include <iostream>
+#include <math.h>
+using namespace std;
+
+// A utility function to get the maximum of two integers
+int max(int a, int b) { return (a > b) ? a : b; }
+
+/* Returns the best obtainable price for a rod of length n
+and price[] as prices of different pieces */
+int cutRod(int price[], int index, int n)
+{
+	// base case
+	if (index == 0) {
+		return n * price[0];
+	}
+	//At any index we have 2 options either
+	//cut the rod of this length or not cut
+	//it
+	int notCut = cutRod(price,index - 1,n);
+	int cut = INT_MIN;
+	int rod_length = index + 1;
+
+	if (rod_length <= n)
+		cut = price[index]
+			+ cutRod(price,index,n - rod_length);
+
+	return max(notCut, cut);
+}
+
+/* Driver program to test above functions */
+int main()
+{
+	int arr[] = { 1, 5, 8, 9, 10, 17, 17, 20 };
+	int size = sizeof(arr) / sizeof(arr[0]);
+	cout << "Maximum Obtainable Value is "
+		<< cutRod(arr, size - 1, size);
+	getchar();
+	return 0;
+}
+
+
