Maximum Ribbon Cut

Problem

Given a ribbon of length n and a list of allowed cut sizes, return the maximum number of pieces that sum exactly to n, or -1 if no combination works.

Use unbounded knapsack DP where dp[x] is the most pieces for length x, trying every cut size at each length. dp[0] = 0 and unreachable lengths stay at -1.

Hint

Prefer smaller pieces for more total pieces, but only if the remainder is reachable.

Test cases

case 1

in: [5,[2,3]]

expected: 2

case 2

in: [7,[2,3]]

expected: 3

case 3

in: [7,[5]]

expected: -1

case 4

in: [9,[2,5]]

expected: 3

case 5

in: [4,[4]]

expected: 1

case 6

in: [0,[1]]

expected: 0

Starter codePython

def max_ribbon_cut(n, sizes):
    # Your code here
    pass

6 test cases · run your code against them in the editor