Subset sum or 0-1?

When your values - your a_n - can be negative, and your b (the goal) is zero, then it's called "subset sum". If the a_n are non-negative (i.e., some of the a's may be zero), the b is positive, and the choice is to either exclude (0) or include (1) one "copy" of each value, then it's a "0-1 knapsack" problem. Usually, but not always, a knapsack problem has components with multiple values, and the goal is a minimax problem: maximize the a's, while minimizing the c's.

It's always darkest, just after the lights go out.

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options