Busking Set List

Mediumdynamic programmingAlso known as 0/1 Knapsack

A street musician has a slot at a weekend market, and the slot is a fixed number of minutes. From past weekends she knows, for each song she can play, how long it lasts and roughly how much money it brings in. Crowds get bored of repeats, so she plays each song at most once.

Which songs should she pick so the set fits in the slot and earns the most?

Your task

Write maxTips(lengths, tips, limit). Song i lasts lengths[i] minutes and earns tips[i]. Choose any set of songs, each used at most once, with total length at most limit, and return the largest possible total of tips.

The order of songs does not matter, and she may leave time unused. With no songs, or if nothing fits, return 0.

maxTips(lengths: int[], tips: int[], limit: int) → int

Examples

Example 1

Input

lengths = [5, 4, 3]
tips = [10, 7, 6]
limit = 7

Output

Why

The 4-minute and 3-minute songs fit exactly and earn 7 + 6 = 13. Starting with the best earner, the 5-minute song for 10, leaves 2 minutes, where nothing fits. The best single song is not part of the best set.

Example 2

Input

lengths = [2, 6]
tips = [5, 11]
limit = 6

Output

Why

Playing the 2-minute song three times would earn 15, but each song can be played only once. The choice is 5 or 11, so 11.

Constraints

0 ≤ lengths.length = tips.length ≤ 100
1 ≤ lengths[i] ≤ 1,000
0 ≤ tips[i] ≤ 10,000
0 ≤ limit ≤ 1,000

Start with brute force

Try every subset of songs, keep those that fit, and take the best total. That is 2ⁿ subsets: about a million for 20 songs, and an impossible 10³⁰ for 100.

Greedy rules are tempting and wrong. Picking the best earner first takes the 5-minute song in the first example and ends with 10 instead of 13. Picking the best money per minute first also fails: with songs of 1, 5 and 5 minutes earning 3, 10 and 10 and a 10-minute slot, it grabs the 1-minute song first and ends with 13 instead of 20.

Hints

0 of 4 shown

Hint 1
Look at the last song in the list. In the best set, either she plays it or she does not. If she plays it, what changes about the problem that is left?
Hint 2
If she skips it, the answer is the best set from the other songs with the same limit. If she plays it, she earns its tip and the rest must come from the other songs with limit - length minutes. So the state is two numbers: how many songs you have considered, and how many minutes are left.
Hint 3
Build a table best[t] = most money from the songs considered so far using at most t minutes. Start with all zeros (no songs). Add songs one at a time.
Hint 4
For each song, update best[t] = max(best[t], best[t - length] + tip) for every t from limit down to length. Going downward means best[t - length] still describes the set without this song, so it cannot be played twice.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Each song is a yes-or-no decision. The best set using the first few songs and t minutes is either the same as without the newest song, or the newest song plus the best set of the earlier songs in t - length minutes.

Trace the first example: lengths [5, 4, 3], tips [10, 7, 6], limit 7. The table holds best[0..7]:

Start: [0, 0, 0, 0, 0, 0, 0, 0].
Song (5 min, 10): for t = 7, 6, 5, best[t] = max(0, best[t - 5] + 10) = 10. Table: [0, 0, 0, 0, 0, 10, 10, 10].
Song (4 min, 7): t = 7: max(10, best[3] + 7 = 7) = 10. t = 6, 5: stay 10. t = 4: max(0, best[0] + 7) = 7. Table: [0, 0, 0, 0, 7, 10, 10, 10].
Song (3 min, 6): t = 7: max(10, best[4] + 6 = 13) = 13. t = 6: max(10, best[3] + 6 = 6) = 10. t = 5: 10. t = 4: max(7, best[1] + 6 = 6) = 7. t = 3: 6.

The answer is best[7] = 13. In the last step, best[4] was 7, the 4-minute song alone, which is exactly the set the 3-minute song joins.

Reference solution

function maxTips(lengths, tips, limit) {
  // best[t] = most money from the songs seen so far in at most t minutes
  const best = new Array(limit + 1).fill(0);
  for (let i = 0; i < lengths.length; i++) {
    // go downward so best[t - len] does not already include song i
    for (let t = limit; t >= lengths[i]; t--) {
      best[t] = Math.max(best[t], best[t - lengths[i]] + tips[i]);
    }
  }
  return best[limit];
}

def max_tips(lengths, tips, limit):
    # best[t] = most money from the songs seen so far in at most t minutes
    best = [0] * (limit + 1)
    for length, tip in zip(lengths, tips):
        # go downward so best[t - length] does not already include this song
        for t in range(limit, length - 1, -1):
            best[t] = max(best[t], best[t - length] + tip)
    return best[limit]

TimeO(n × limit)For each of the n songs, one pass over the minutes from limit down.

SpaceO(limit)One row of the table, reused for every song.

Learn the idea: Knapsack 1D Dynamic Programming

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code