PROBLEM STATEMENT:
We are given a rod with a given length. We can cut in infinite number of pieces. We are given a price array and a length array, the price of each length is given in the price array in the corresponding index. We have to determine maximum price to cut the rod.
QUICK POINTS:
1. The total sum of length will be equal to the given length and each length has a definite price, which is given in the price array. We have to determine maximum price.
2. We can cut into pieces of same length, so the problem is a variation unbounded knapsack.
STEPS:
1. We are taking input n, len, length[n], price[n] as size of array, total length of the array, array of length and array of price corresponding to each length.
2. Now, we are creating a matrix of size (n+1)*(len+1).
3. If either current length is zero or there is no price, the maximum price will be zero, which is the initialization of the problem.
4. If current length (length[i-1]) is greater than the remaining length of the rod we cannot obtain a piece of length length[i-1] by cutting, so will be exclude this.
If current length is less than the remaining length of rod we can either cut it in a piece of that length or we can exclude it depending upon the price obtained.
CODE:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int len,n;
cin>>len>>n;
int price[n],length[n];
for(int i=0;i<n;i++)
cin>>length[i];
for(int i=0;i<n;i++)
cin>>price[i];
int dp[n+1][len+1];
for(int i=0;i<n+1;i++)
{
for(int j=0;j<len+1;j++)
{
if(i==0|| j==0)
dp[i][j]=0;
else if(length[i-1]<=j)
dp[i][j]=max(price[i-1]+dp[i][j-length[i-1]],dp[i-1][j]);
else if(length[i-1]>j)
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][len]<<endl;
return 0;
}
INPUT:
6 5
1 2 3 4 5
4 5 6 7 8
OUTPUT:
24
0 Comments