Cut Ribbon Problem - Sanfoundry

This is a C++ Program that Solves Cut the Ribbon Problem using Dynamic Programming technique.

Problem Description

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.

Problem Solution

This seems like a greedy problem but actually is a DP problem. We will create an array dp[] to memoize values.

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

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.

Expected Input and Output

Case-1:

 
n=5
a=5
b=3
c=2
 
Expected result=2 (5=3+2)

Case-2:

Participate in Data Structure I Certification Contest of the Month Now!

 
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)

Program/Source Code

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;
```
```
}
```

Program Explanation

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.

Runtime Test Cases

 
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.

« Prev - T-Primes Problem using Dynamic Programming

» Next - Non Decreasing Digits Problem – Dynamic Programming Solutions

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs
Buy Computer Science Books
Apply for Computer Science Internship

Recommended Articles: