Maximum Ribbon Cut

Introduction

• 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

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:

import math


def count_ribbon_pieces(ribbonLengths, total):
    maxPieces = count_ribbon_pieces_recursive(ribbonLengths, total, 0)
    return -1 if maxPieces == -math.inf else maxPieces


def count_ribbon_pieces_recursive(ribbonLengths, total, currentIndex):
    # base check
    if total == 0:
        return 0

    n = len(ribbonLengths)
    if n == 0 or currentIndex >= n:
        return -math.inf

    # recursive call after selecting the ribbon length at the currentIndex
    # if the ribbon length at the currentIndex exceeds the total, we shouldn't process this
    c1 = -math.inf
    if ribbonLengths[currentIndex] <= total:
        result = count_ribbon_pieces_recursive(
            ribbonLengths, total - ribbonLengths[currentIndex], currentIndex)
        if result != -math.inf:
            c1 = result + 1

    # recursive call after excluding the ribbon length at the currentIndex
    c2 = count_ribbon_pieces_recursive(ribbonLengths, total, currentIndex + 1)
    return max(c1, c2)


def main():
    print(count_ribbon_pieces([2, 3, 5], 5))
    print(count_ribbon_pieces([2, 3], 7))
    print(count_ribbon_pieces([3, 5, 7], 13))
    print(count_ribbon_pieces([3, 5], 7))


main()

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:

import math


def count_ribbon_pieces(ribbonLengths, total):
    n = len(ribbonLengths)
    dp = [[-math.inf for _ in range(total+1)] for _ in range(n)]

    # populate the total=0 columns, as we don't need any ribbon to make zero total
    for i in range(n):
        dp[i][0] = 0

    for i in range(n):
        for t in range(1, total+1):
            if i > 0:  # exclude the ribbon
                dp[i][t] = dp[i - 1][t]
            # include the ribbon and check if the remaining length can be cut into available lengths
            if t >= ribbonLengths[i] and dp[i][t - ribbonLengths[i]] != -math.inf:
                dp[i][t] = max(dp[i][t], dp[i][t - ribbonLengths[i]] + 1)

    # total combinations will be at the bottom-right corner, return '-1' if cutting is not possible
    return -1 if dp[n - 1][total] == -math.inf else dp[n - 1][total]


def main():
    print(count_ribbon_pieces([2, 3, 5], 5))
    print(count_ribbon_pieces([2, 3], 7))
    print(count_ribbon_pieces([3, 5, 7], 13))
    print(count_ribbon_pieces([3, 5], 7))


main()

Next