This is a C++ Program that Solves Cut the Ribbon Problem using Dynamic Programming technique.
Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:
After the cutting each ribbon piece should have length a, b or c.
After the cutting the number of ribbon pieces should be maximum.
Help Polycarpus and find the number of ribbon pieces after the required cutting.
Constraints-
1 <= n, a, b, c <= 4000
The numbers a, b and c can coincide.
This seems like a greedy problem but actually is a DP problem. We will create an array dp[] to memoize values.
dp[i]=number of ribbon peices for n=i
We will initialize dp[0]=0 and then proceed in a bottom up fashion to tabulate the array.
Case-1:
n=5 a=5 b=3 c=2 Expected result=2 (5=3+2)
Case-2:
n=7 a=5 b=5 c=2 Expected result=2 (7=5+2)
Case-3:
n=16 a=7 b=5 c=3 Expected result=4 (16=7+3+3+3)
Here is source code of the C++ Program to solve Cut the Ribbon problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
//cut the ribbon
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,k,n;
int a,b,c;
int x,y,z;
cout<<"Enter the length of ribbon"<<endl;
cin>>n;
cout<<"Enter the 3 values of lengths allowed"<<endl;
cin>>a>>b>>c;
//array to memoize values
vector<int> dp(n+1);
//initialize
dp[0]=0;
for(i=1;i<=n;i++)
{
x=y=z=-1;
if(i>=a)
x=dp[i-a];
if(i>=b)
y=dp[i-b];
if(i>=c)
z=dp[i-c];
if(x==-1 && y==-1 && z==-1)
dp[i]=-1;
else
dp[i]=max(max(x,y),z)+1;
}
if(dp[n]==-1)
cout<<"Not possible";
else
cout<<"Maximum number of pieces in which the ribbon can be cut is "<<endl<<dp[n];
cout<<endl;
return 0;
}
In the main function, we take input for n, a, b, c. Then, we create an array to fill it in bottom up manner. After tabulating the array, the result is displayed.
Case-1: $ g++ cut_the_ribbon.cpp $ ./a.out Enter the length of ribbon 5 Enter the 3 values of lengths allowed 5 3 2 Maximum number of pieces in which the ribbon can be cut is 2 Case-2: $ ./a.out Enter the length of ribbon 7 Enter the 3 values of lengths allowed 5 5 2 Maximum number of pieces in which the ribbon can be cut is 2 Case-3: $ ./a.out Enter the length of ribbon 16 Enter the 3 values of lengths allowed 7 5 3 Maximum number of pieces in which the ribbon can be cut is 4
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Programming MCQs
- Check Programming Books
- Practice Design & Analysis of Algorithms MCQ