Take or Skip With a Target

If you learn one DP pattern well, make it this one.

The shape

• Each item can be used at most once.
• There is a target: a sum, a budget or a capacity.
• Taking an item uses up part of the target.

f(i, rem) = the answer using items i..n-1, when rem is what's left of the target

• take item i (only if it fits) → f(i + 1, rem − w[i])
• skip item i → f(i + 1, rem)