如何切出最大长度乘积MaximumProductCutting@geeksforgeeks

转自出处

Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters.

Examples:

Input: n &＃61; 2
Output: 1 (Maximum obtainable product is 1*1)Input: n &＃61; 3
Output: 2 (Maximum obtainable product is 1*2)Input: n &＃61; 4
Output: 4 (Maximum obtainable product is 2*2)Input: n &＃61; 5
Output: 6 (Maximum obtainable product is 2*3)Input: n &＃61; 10
Output: 36 (Maximum obtainable product is 3*3*4)

1) Optimal Substructure: 
This problem is similar to Rod Cutting Problem. We can get the maximum product 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 maxProd(n) be the maximum product for a rope of length n. maxProd(n) can be written as following.

maxProd(n) &＃61; max(i*(n-i), maxProdRec(n-i)*i) for all i in {1, 2, 3 .. n}

2) Overlapping Subproblems
Following is simple recursive C&＃43;&＃43; implementation of the problem. The implementation simply follows the recursive structure mentioned above.

A Tricky Solution:
If we see some examples of this problems, we can easily observe following pattern.
The maximum product can be obtained be repeatedly cutting parts of size 3 while size is greater than 4, keeping the last part as size of 2 or 3 or 4. For example, n &＃61; 10, the maximum product is obtained by 3, 3, 4. For n &＃61; 11, the maximum product is obtained by 3, 3, 3, 2. Following is C&＃43;&＃43; implementation of this approach.

[java] view plaincopy

1. package DP;  
2.   
3. public class MaxProductCutting {  
4.   
5.     public static void main(String[] args) {  
6.         System.out.println(maxProdRec(10));  
7.         System.out.println(maxProdDP(10));  
8.         System.out.println(maxProdTrick(10));  
9.     }  
10.       
11.     public static int maxProdRec(int n){  
12.         if(n&＃61;&＃61;0 || n&＃61;&＃61;1){  
13.             return 0;  
14.         }  
15.         int max &＃61; 0;  
16.         for(int i&＃61;1; i
17.             // 1.只切一刀  2.切完一刀后&＃xff0c;把余下的继续切  
18.             int bigger &＃61; Math.max(i*(n-i), i*maxProdRec(n-i));  
19.             max &＃61; Math.max(max, bigger);  
20.         }  
21.           
22.         return max;  
23.     }  
24.       
25.     // Time: O(n^2), space:O(n)  
26.     public static int maxProdDP(int n){  
27.         // maxProd[i]: 总长度为i的绳子能切出的最大乘积  
28.         int[] maxProd &＃61; new int[n&＃43;1];  
29.         maxProd[0] &＃61; maxProd[1] &＃61; 0;  
30.           
31.         // Build the table maxProd[] in bottom up manner and return  
32.         // the last entry from the table  
33.         for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){     // 总长度为i  
34.             int max &＃61; 0;  
35.             for(int j&＃61;1; j<&＃61;i/2; j&＃43;&＃43;){   // 切长度为j  
36.                 int bigger &＃61; Math.max(j*(i-j), j*maxProd[i-j]);  
37.                 max &＃61; Math.max(max, bigger);  
38.             }  
39.             maxProd[i] &＃61; max;  
40.         }  
41.         return maxProd[n];  
42.     }  
43.       
44.     // 规律&＃xff1a;不断以3为单位长度切  
45.     public static int maxProdTrick(int n){  
46.         if(n&＃61;&＃61;2 || n&＃61;&＃61;3){       // n equals to 2 or 3 must be handled explicitly  
47.             return n-1;  
48.         }  
49.         int res &＃61; 1;  
50.         while(n > 4){        // Keep removing parts of size 3 while n is greater than 4  
51.             n -&＃61; 3;  
52.             res *&＃61; 3;       // Keep multiplying 3 to res  
53.         }  
54.         return n*res;       // The last part multiplied by previous parts  
55.     }  
56.   
57. }