Standard Bar Dynamic Programming · DP on Subsequences O(n*W) · O(W)
A distributor loads a delivery van with stock items — each SKU has a boxed weight and a resale margin, and the storeroom holds unlimited copies of every SKU. The van has a hard axle limit W. The buyer's terminal must pick the basket of SKUs (repeats allowed) that maximizes margin without exceeding the limit.
Input: Integers n and W, plus arrays wt and val of length n giving each SKU's weight and value.
Output: Return the maximum total value with total weight at most W, where any item may be taken any number of times.
1 <= n <= 10^31 <= W <= 10^31 <= wt[i], val[i] <= 10^3Input: {"n":2,"W":3,"wt":[2,1],"val":[1,1]}
Output: 3
Load the weight-1 item three times — total 3 within the limit.
Input: {"n":3,"W":8,"wt":[2,3,5],"val":[3,4,7]}
Output: 12
Four copies of the weight-2 SKU load the van to exactly 8 for 4 * 3 = 12.