Consider the following variant of the rod-cutting problem, where for every i les
ID: 3573759 • Letter: C
Question
Consider the following variant of the rod-cutting problem, where for every i lessthanorequalto n, we can sell a piece of size i only once. (Thus once we cut a piece of size, say 3, then theres no further demand of pieces of size 3, so we dont want to cut anymore of that size.) For example, suppose that our rod has length n = 5, and the price table is P[1] = 1, P[2] = 3, P[3] = 4, P[4] = 7, P[5] = 2. If you cut the rod into three pieces of size 2, 2, and 1, your profit is P[1] + P[2] = 4. If you cut the rod into five pieces of size 1, then your profit is only P[1] = 1. If you cut the rod into two pieces of size 2 and 3, your profit is P[2] + P[3] = 7 as usual. Give an efficient dynamic programming algorithm to find the optimal profit, and analyze its running time. We cut the rod into m pieces of length x_1, ..., x_m, with x_1 > x_2 > ... > x_m greaterthanorequalto 1, and sell all of them. In this case youll get profit P[x_1] + ... + P[x_m]. (This includes the special case theres no cut, meaning you sell the rod as a whole.) We cut the rod into m pieces of length x_1, ..., x_m, with x_1 > x_2 > .... > x_m - 1 greaterthanorequalto 1, and sell all except the last piece x_m. Youll get profit P[x_1] + ... + P[x_m - 1]. Although technically its a different problem, the optimal profit in this case is exactly the same as before. To see why, for example, if n = 5 and you cut the rod to five pieces of length n, youll get the same profit if you cut two pieces x_1 = 1 and x_2 = 4, and sell just the first piece. If n = 5 and you cut the rod into pieces of length 1, 2, 2, youll get the same profit if you cut three pieces x_1 = 2, x_2 = 1, x_3 = 2, and sell just the first two pieces. If n = 5 and you cut the rod into pieces of length 2 and 3, youll get the same profit if you cut into pieces x_1 = 3, x_2 = 2, and sell all of them. To solve the new problem, youll need to consider a two-dimensional array A[-, middot], and the total running time will be O(n^3).Explanation / Answer
Below is the JAVA code implementation for the Dynamic solution.
// Here price is the array of prices given i.e. 1,3,4,7,2.
public int dpSolution(int price[]){
int max[] = new int[price.length+1];
for(int i=1; i <= price.length; i++){
max[i] = price[i-1];
}
for(int i=1 ; i <= price.length; i++){
for(int j=1; j < i ; j++){
// Checking for prices with duplicate values like 2,2
if(max[i-j] != max[j])
max[i] = Math.max(max[i], max[i-j] + max[j]);
}
}
return max[price.length];
}