Cutting a Rod

Cutting a Rod

Tushar Roy Video 

Medium blog post 

Implementation 01:

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int cutRod(int price[], int n)
	{
	if (n <= 0) return 0;
	int mx = INT_MIN;
	for (int i = 0; i < n; i++)
	mx = max(mx, price[i] + cutRod(price, n - i - 1));
	return mx;
	}
	/// O(n^2)
	vector<int> rods;
	int cutRodDp(int price[], int n)
	{
	int dp[n + 1];
	int lastRod[n + 1];
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
	int mx = INT_MIN;
	int best_rod_len = -1;
	for (int j = 0; j < i; j++) {
	if (mx < price[j] + dp[i - j - 1]) {
	mx = price[j] + dp[i - j - 1];
	best_rod_len = j;
	}
	//mx = max(mx, price[j] + dp[i - j - 1]);
	}
	dp[i] = mx;
	lastRod[i] = best_rod_len + 1;
	}
	for (int i = n; i > 0; i -= lastRod[i]) {
	rods.push_back(lastRod[i]);
	}
	return dp[n];
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	int a[] = {1, 5, 8, 9, 10, 17, 17, 20};
	int n = sizeof(a) / sizeof(a[0]);
	cout << cutRod(a, n) << "\n";
	cout << cutRodDp(a, n);
	cout << " { ";
	for (auto x : rods) cout << x << " ";
	cout << "}\n";
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw cuttingRod.cpp hosted with ❤ by GitHub

 

 Aplication:

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int Max(int a, int b, int c) { return max(a, max(b, c));}
	int maxCuttingProduct(int n)
	{
	if (n == 0 || n == 1) return 0;
	int mx = 0;
	for (int i = 1; i < n; i++) {
	mx = Max(mx, i * (n - i), maxCuttingProduct(n - i) * i);
	}
	return mx;
	}
	int maxCuttingProductDp(int n)
	{
	int dp[n + 1];
	dp[0] = dp[1] = 0;
	for (int i = 1; i <= n; i++) {
	int mx = 0;
	for (int j = 1; j <= i / 2; j++)
	mx = Max(mx, (i - j) * j, j * dp[i - j]);
	dp[i] = mx;
	// dbg2(dp[i], i);
	}
	return dp[n];
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	int n;
	cin >> n; // 10
	cout << maxCuttingProduct(10) << endl; // 36 (3 * 3 * 4)
	cout << maxCuttingProductDp(10) << endl;
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Maximum Product Cutting.cpp hosted with ❤ by GitHub

 

Share: