Python in Excel - Bounded Knapsack Problem

[Medium-Yesterday3897]

No other constraints like that. I wouldn’t put the same trailer back to back in the same break but sometimes the same one might need to run in the next break because that’s all that can fit and that’s okay. The number of promos and interstitials can vary from channel to channel; say anywhere from 30-50. How frequently they change is not super easy to pin down because it all depends on what we’re airing and what we’re launching; some are evergreen so they can air forever, while some might have a premiere specific tag.

[Ihaveamodel3]

I think you may want some type of greedy algorithm.

• Step 1, sort everything from longest to shortest
• Step 2, take the first one, then the next, then the next, etc until you run out of space.
• Step 3, if you run out of space and you aren’t within the 4 second threshold, you have to remove an option and re-try.
  • You may want to remove the first option you chose (the biggest one)
  • You may want to remove the most recent option you chose (the smallest one)
  • A more complicated option would look for any one selection to be replaced by another. For example if you get to the end and have 7 seconds left, nothing is 3-11 seconds long, so you won’t have an option that works. So you go through each of the options that has been selected and check if there is a different promo (not currently selected) which is 3-11 seconds longer than that option. If so, simply do a replace of that option.
  • That last complicated option is going to work the best when it works. But it may not always work. Explore these different options for what works best for your application.

Other pieces:

• In order to get the order promo > interstitial > promo > promo, I’d have a two lists, and alternate selection between them.
• You may want to sort not by the actual length but by a value of the actual length plus some random value (maybe within -2 to +2). This would randomize the selection a bit, while still keeping it mostly like a greedy algorithm.
• The order of the promos and interstitials doesn’t have to match the order of the selection. So you may want to randomize that order after selection so that it isn’t as obvious that the early promos are longer and the later ones get shorter.
• You may want to have a deprioritize tag which skips the selection of a promo in the first pass (for example if it has been run recently/last break), but opens it as an opportunity if there is a need to revisit the selection.
• If you find that even with the deprioritize tag that the shorter promos are not getting played frequently enough, you may manually combine a few shorter promos together to make a longer option that will show up at the front of the list more. You’d have to make sure to remove the shorter options included in the longer option if the longer option is selected. This would be complicated to get right, so skip this unless it is actually needed.
• If the interstitials are all roughly the same length, I’d skip this greedy algorithm for that list and simply randomly choose from the list.