PROBLEM LINK:
Author: samhenry97
Editorialist: samhenry97
DIFFICULTY:
Easy
PREREQUISITES:
PROBLEM:
What is the largest amount of items of an array that sums to a number <= a given value?
QUICK EXPLANATION:
We can construct a sum array, and then use binary searches for each query.
EXPLANATION:
First, we read the integers and sort them. Then, we create an array sum, which is a cache of the sums of each subarray 0…i.
Now, for each query, we can run a binary search to see where the largest sum is that fits the weight.