Solution: Maximum Ribbon Cut

Grokking Dynamic Programming Patterns for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Maximum Ribbon Cut

Table of Contents

Contents are not accessible

Introduction

We are given a ribbon of length ‘n’ and a set of possible ribbon lengths. We need to cut the ribbon into the maximum number of pieces that comply with the above-mentioned possible lengths. Write a method that will return the count of pieces.

Example 1:

n: 5
Ribbon Lengths: {2,3,5}
Output: 2
Explanation: Ribbon pieces will be {2,3}.

Example 2:

n: 7
Ribbon Lengths: {2,3}
Output: 3
Explanation: Ribbon pieces will be {2,2,3}.

Example 3:

n: 13
Ribbon Lengths: {3,5,7}
Output: 3
Explanation: Ribbon pieces will be {3,3,7}.

Problem Statement

Given a number array to represent possible ribbon lengths and a total ribbon length 'n,' we need to find the maximum number of pieces that the ribbon can be cut into.

Try it yourself

Try solving this question here:

Python3

. . . .

This problem follows the "Unbounded Knapsack" pattern and is quite similar to "Minimum Coin Change" (MCC). The only difference is that in MCC, we were asked to find the minimum number of coin changes, whereas, in this problem, we need to find the maximum number of pieces.

Basic Solution

A basic brute-force solution could be to try all combinations of the given lengths to select the maximum one that gives the total length of 'n.' This is what our algorithm will look like:

for each length 'l' 
  create a new set which includes one quantity of length 'l' if it does not exceed 'n', and 
     recursively call to process all lengths 
  create a new set without length 'l', and recursively call to process the remaining lengths
return the number of pieces from the above two sets with a higher number of pieces

Code

Here is the code for the brute-force solution:

Python3

. . . .

The above algorithm's time complexity is exponential $O(2^{L+N})$ , where 'L' represents total ribbon lengths, and 'N' is the total length that we want to cut. The space complexity will be $O(L+N)$ .

Since this problem is quite similar to Minimum Coin Change, let's jump on to the bottom-up dynamic programming solution.

Bottom-up Dynamic Programming

Let's try to populate our array dp[ribbonLength][total+1] for every possible ribbon length with a maximum number of pieces.

So for every possible length ‘len’ (0 <= len <= total) and for every possible ribbon length index (0 <= index < ribbonLengths.length), we have two options:

Exclude the ribbon length: In this case, we will take the maximum piece count from the previous set => dp[index-1][len]
Include the ribbon length if its value is not more than ‘len’: In this case, we will take the maximum pieces needed to get the remaining total, plus include '1' for the current ribbon length => 1 + dp[index][len-ribbonLengths[index]]

Finally, we will take the maximum of the above two values for our solution:

    dp[index][len] = max(dp[index-1][len], 1 + dp[index][len-ribbonLengths[index]])

Code

Here is the code for our bottom-up dynamic programming approach:

Python3

. . . .

The above solution has time and space complexity of $O(L*N)$ , where 'L' represents total ribbon lengths and 'N' is the total length that we want to cut.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible