Geeks面试题： Cutting a Rod

Cutting a Rod

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n.Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

The naive solution for this problem is to generate all configurations of different pieces and find the highest priced configuration. This solution is exponential in term of time complexity. Let us see how this problem possesses both important properties of a Dynamic Programming (DP) Problem and can efficiently solved using Dynamic Programming.

Optimal Substructure:
We can get the best price by making a cut at different positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut.

Let cutRoad(n) be the required (best possible price) value for a rod of lenght n. cutRod(n) can be written as following.

cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}

要根据上面的公式进行思考，形成抽象思维，和系统思维。

这种抽象能力非常难，也非常重要，直接决定了效率，甚至能否做出来的问题。

优秀的程序员和普通程序员之间的差距也许就从抽象思维能力中分出来了。

不过慢慢对动态规划法和递归回溯法熟悉了，其实就可以撇开什么公式和递归回溯，直接从表入手，填表，把表翻译为程序也是个很不错的做法。

程序1：

int cutRod(int price[], int n)
{
	vector<int> ta(n+1);
	for (int i = 1; i <= n; i++)
	{
		ta[i] = price[i-1];
		for (int j = 1; j < i/2+1; j++)
		{
			ta[i] = max(ta[i], ta[j]+ta[i-j]);
		}
	}
	return ta[n];
}

程序2：动态规划和递归

int cutRodDP(int price[], int n)
{
	vector<int> ta(n+1);
	for (int len = 1; len <= n; len++)
	{//这里代表长度
		int maxPrice = price[len-1];//长度问len的时候，值cut一段的价格
		for (int cut = len-2; cut >= 0; cut--)
		{//price[cut]代表cut出了cut长度的价格，然后余下的继续cut
			maxPrice = max(maxPrice, price[cut] + ta[len-cut-1]);
		}
		ta[len] = maxPrice;
	}
	return ta[n];
}


/* Returns the best obtainable price for a rod of length n and
price[] as prices of different pieces */
int cutRod(int price[], int n)
{
	if (n <= 0)
		return 0;
	int max_val = INT_MIN;

	// Recursively cut the rod in different pieces and compare different 
	// configurations
	for (int i = 0; i<n; i++)
		max_val = max(max_val, price[i] + cutRod(price, n-i-1));

	return max_val;
}

int main()
{
	int arr[] = {1, 5, 8, 9, 10, 17, 17, 20};
	int size = sizeof(arr)/sizeof(arr[0]);
	printf("Maximum Obtainable Value is %d\n", cutRod(arr, size));

	cout<<cutRodDP(arr,size)<<endl;

	system("pause");
	return 0;
}