Maximum Ribbon Cut
Understand how to maximize the number of ribbon pieces cut from a given length using dynamic programming approaches. Explore a naive recursive solution, then improve efficiency with memoization and tabulation methods to optimize for time and space complexity.
Statement
Given a ribbon of length n and a set of possible sizes, cut the ribbon in sizes such that n is achieved with the maximum number of pieces.
You have to return the maximum number of pieces that can make up n by using any combination of the available sizes. If the n can’t be made up, return -1, and if n is 0, return 0.
Let’s say, we have a ribbon of length and possible sizes as . The ribbon length can be obtained by cutting it into one piece of length and another of length (as ), or, into one piece of length and two pieces of length (as ). As we wish to maximize the number of pieces, we choose the second option, cutting the ribbon into pieces.
Constraints:
-
sizes.length -
sizes[i] -
n...
No. | n | sizes | Count of Pieces |
1 | 5 | [1, 2, 3] | 5 |
2 | 13 | [5, 3, 8] | 3 |
3 | 3 | [5] | -1 |
Try it yourself
Implement your solution in the following playground:
function countRibbonPieces(n, sizes){// write your code herereturn -1;}export {countRibbonPieces};
...