Find max obtainable price by selling
pieces of a rod
Given
a rod of length ‘targetSize’
Given
an array of prices where price at each index is the price obtained by
selling rod of length equal to that index.
Find
out the max price which can be obtained by selling pieces of that
rod.
Solution:
This is very similar to the above problem with some important
differences.
If
we had price available for only one size, then max price obtainable
for any ‘targetSize’ is easy. We can create a lookup
table (rather a lookup array) which will store the max price
obtainable if there were only one price available.
Let
maxPrice be that array whose every index will store max price
obtainable for target-size equal to that index.
maxPrice[0]
= 0 // if target-Size is 0, then we cannot sell it, hence max price
is 0
maxPrice[1]
= prices[1]; // assuming price[0] is 0 to make calculation easier.
maxPrice[2]
= prices[1] + maxPrice[1];
maxPrice[3]
= prices[1] + maxPrice[2];
Now,
if we had one more price available, then the above maxPrice array
will need to have a second pass where the max price obtainable at
every target-Size is changed if the introduction of newly added price
fetches higher value.
Second
pass is as follows:
maxPrice[0]
= 0;
maxPrice[1]
= prices[1]; // price of size 2 cannot affect max-prices of sizes
less than 2
maxPrice[2]
= MAX ( maxPrice[2] , prices[2] ) ;
maxPrice[3]
= MAX ( maxPrice[3] , prices[2] + maxPrice[1]);
If
we now introduce the third price, then fourth and so on, we will need
to make that many passes on the above array.
maxPrice[targetSize]
will then give us the required answer.
Without
dynamic programming, recursive solution for the above would have
computed solutions to the same problem again and again as follows:
Note:
The above does not consider the case when (targetSize-i) is less than
0. In that case, the recursive call returns 0 which is added to
prices[i] in the parent calling function. This is incorrect, since we
cannot sell a piece which is larger than the remaining size.
So,
if price array was [1, 5, 3, 200] and target-size was 100, above will
return 200 even though we cannot sell rod of size 200 in this case.
This
can be eliminated by putting in a check for i < targetSize.
Dynamic
programming eliminates the repeated recursion by using a table
look-up as follows:
(Observe
the above check has been put in this implementation)
int findMaxPrice (int prices [], int maxRodSize)
{
if (maxRodSize <= 0 || prices.length <= 0)
return 0;
int maxPriceForSizeK[maxRodSize+1] = {0};
// outer loop introduces each size/price one by one
for (int nextSize=1; nextSize <= prices.length; nextSize++)
{
// inner loop finds the effect of introduction of each size/price
// on max-price available till now with previous sizes/prices.
for (int S=nextSize; S<=maxRodSize; S++)
{
if (nextSize > S && maxPriceForSizeK[S-nextSize] > 0)
{
maxPriceForSizeK[S] = Math.max (
maxPriceForSizeK[S],
prices[nextSize] + maxPriceForSizeK[S - nextSize]
);
}
}
}
return maxPriceForSizeK[maxRodSize];
}
|