Cargo Too Heavy to Tabulate

A cargo plane can carry at most capacity kilograms. There are n crates; crate i weighs weights[i] kilograms and earns values[i] euros when delivered. Each crate is either loaded whole or left behind.

Write best_load(weights, values, capacity) that returns the largest total value of a set of crates whose total weight is at most capacity. Loading nothing is allowed (value 0).

The weights, values and capacity are huge numbers, so a table with one entry per kilogram (or per euro) is far too big, and with 34 crates there are more than 17 billion sets to choose from.

The larger tests use crates(n, seed), available in your code, which returns a tuple (weights, values, capacity); call it as best_load(*crates(30, 2)).

Examples

Input:  weights = [5, 4, 6, 3], values = [10, 40, 30, 50], capacity = 10
Output: 90
Explanation: crates 1 and 3 weigh 4 + 3 = 7 and earn 40 + 50 = 90.

Input:  weights = [1000000000, 600000000, 500000000], values = [7, 5, 4], capacity = 1100000000
Output: 9
Explanation: the two lighter crates together (1.1 billion kg) beat the heaviest one alone.

Input:  weights = [8, 9], values = [100, 100], capacity = 7
Output: 0

Constraints

• 0 <= n <= 34, len(values) == len(weights) == n
• 1 <= weights[i], values[i] <= 10**9
• 0 <= capacity <= 4 * 10**10

Goals

• See why a table indexed by weight fails when weights are huge
• Split a search over subsets into two halves and combine them
• Remove dominated partial solutions and combine halves with binary search