This problem was used in the following GFU competitions:
GFU 2024 D2 Q11
You like deadlifting, but you feel your deadlifts are not glamorous enough for your new hobby of gym blogging on Instagram. You need to find out the highest "value" (how pretty a weight is) you can lift for your followers while still staying below your maximum deadlift weight. You would like to be able to lift the most "value" that you can.
The first input is a single integer x that indicates the number of data sets that follow. Each data set will consist of two integers, n, and w, denoting the number of weights and the max weight that you can deadlift respectively. These two integers will be followed by n integers denoting the "value" of each of the weights, then followed by n integers denoting the weight of each of the weights.
For each data set, output the maximum value that can be obtained by a sum of weights that still fits under the maximum weight you can deadlift. Basically, we are trying to maximize the value we can still feasibly lift, the largest value with weight less than or equal to w.
Example Input:
3
3 10 4 5 6 4 5 6
4 12 7 4 7 9 1 1 3 4
4 20 5 10 15 10 10 12 7 13
Example Output:
10
27
25
Knapsack