Standard Bar Dynamic Programming · DP on Subsequences O(n*W) · O(W)
A rescue helicopter has a strict cargo capacity W, and ground crews have queued up crates, each with a weight and a mission-critical value score. The chopper can lift a crate only whole — no partial loads. The mission planner must choose which crates fly so the rescued value is as high as possible without busting the lift limit.
Input: Integers n and W, plus arrays wt and val of length n holding each crate's weight and value.
Output: Return the maximum total value achievable with total weight at most W, taking each crate at most once.
1 <= n <= 10^31 <= W <= 10^31 <= wt[i], val[i] <= 10^3Input: {"n":3,"W":4,"wt":[4,5,1],"val":[1,2,3]}
Output: 3
Only the third crate fits (weight 1), scoring 3; any heavier crate alone is worth less.
Input: {"n":4,"W":7,"wt":[1,3,4,5],"val":[10,20,30,40]}
Output: 50
Crates weighing 3 and 4 load together for 20 + 30 = 50 at exactly the weight cap.