Problem 694566 · medium · Level 06 Heuristics & Optimization

Festival Lineup on a Budget

genetic algorithm · quadratic knapsack · repair operator · elitism

A small festival books acts under a fixed fee budget. Every act i costs fees[i] and draws appeal[i] visitors on its own, but acts also interact: booking both i and j adds bonus[i][j] (the matrix is symmetric with zeros on the diagonal). Two bands that share a fan base have a negative bonus; a headliner and its usual support act have a positive one.

Write book_acts(inst) that returns a list of distinct act indices whose fees add up to at most inst["budget"], with total appeal (single appeals plus the bonus of every booked pair) as high as you can make it. inst is a dict with the keys "fees", "appeal", "bonus" and "budget".

The tests build their instances with lineup(n, seed), and lineup_value(inst, acts) computes the total appeal of a list of acts. Both are available in your code, so you can try them with Run.

How this problem is scored

A lineup passes if it fits the budget and its total appeal is at least that of the simple rule "sort the acts by appeal per unit of fee, best first, and book each one that still fits" (the rule ignores the pair bonuses). Its quality (0 to 100) is the share of the gap between that rule and the best lineup we know that you close.

Examples

Input:  inst = {"fees": [4, 3, 5, 2], "appeal": [10, 6, 9, 2], "budget": 10,
                "bonus": [[0, -10, 0, 0], [-10, 0, 0, 7], [0, 0, 0, 0], [0, 7, 0, 0]]}
Output: [1, 2, 3]   (fees 10, appeal 6 + 9 + 2 + 7 = 24)
Explanation: the per-fee rule books acts 0, 1 and 3 (appeal 10 + 6 + 2 - 10 + 7 = 15).

Input:  inst = lineup(25, 1)
Output: any list of acts within the budget; better lineups score higher

Constraints

  • 25 <= n <= 120 acts, fees from 2 to 30, appeals from 1 to 30, bonuses from -25 to 30
  • The budget is 30% of the total of all fees.
  • Each test must finish in well under a second in your browser. Limit your loops by a number of rounds or generations, not by the clock, so the result is the same on every run.

Goals

  • Encode a selection problem as a string of bits
  • Keep a population feasible with a repair step
  • Beat a greedy rule that ignores interactions between items
Starting Python…