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.

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:

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

 
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

Related Posts:

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

Recommended Articles: