All problems

Balloon Basket Cheer

Medium · dynamic programming

Zadie is loading the basket of a hot-air balloon for a festival flight. Each entry items[i] = [weight, cheer] describes one thing she could bring along: how many kilograms it weighs and how much cheer it will bring the crowd below.

The basket can lift at most max_weight kilograms in total, and it has hooks for at most max_items things, however light they are. Each thing exists once, so she brings it or leaves it behind.

Return the largest total cheer she can bring along. If nothing fits, return 0.

Examples

Example 1

Input: items = [[3, 40], [2, 30], [4, 45], [1, 10]], max_items = 2, max_weight = 6

Output: 75

The things weighing 2 kg and 4 kg give 75 cheer. Bringing the 3 kg, 2 kg and 1 kg things would give 80, but that is three things and there are only two hooks.

Example 2

Input: items = [[5, 100]], max_items = 3, max_weight = 4

Output: 0

The only thing is too heavy.

Example 3

Input: items = [[1, 7], [1, 8], [1, 9]], max_items = 5, max_weight = 2

Output: 17

There are hooks for all three, but the weight limit allows only two: the best are 8 and 9.

Constraints