# Minimize a sum with a weight constraint

We are given N sets, each of which has a finite number of pairs $(x_i,y_i)$.

$M_1=\{(0,0), (x_{1,1},y_{1,1}), ...\}$

...

$M_N=\{(0,0), (x_{1,N},y_{1,N}), ...\}$

The problem is to select one and only one item from each set such that

$Min \{\displaystyle\sum_{j=1...N}(x_{i,j})\}$

s.t. $\displaystyle\sum_{j=1..N}(y_{i,j}) > R$

where $R$ is a given constant.

Is there any classic problem similar to this? or what is known about this class of problems?

• It's a generalization of KNAPSACK. – Yuval Filmus Mar 4 '16 at 10:03

The problem you have given is similar to KNAPSACK as Yuval Filmus mentioned.

KNAPSACK problem is defined as:

maximize $\sum_{i=1}^n v_i x_i$
subject to $\sum_{i=1}^n w_i x_i \leq W$ and $x_i \in \{0,1\}.$

I assume the pair (0,0) is used so that you may not choose pairs for some of the $M_j$'s. Otherwise (0,0) pair is irrelevant in the problem.

If this is so, then your problem can be easily shown to be NP-complete. We can reduce KNAPSACK to your problem by taking $N=n$ and have each $M_j$ as a copy to the KNAPSACK instance (after negating $v_i$'s and $w_i$'s of course).

If pair (0,0) is not used in a way that I described above, then too you can circumvent the issue by adding $N$ pairs $(x_{N+i,j},y_{N+i,j})$, for $1\leq i \leq N$ in set $M_j$ for $1 \leq j \leq N$, so that each $M_j$ has now additional $N$ pairs (total of $2N+1$). Each $x_{N+i,j} = y_{N+i,j} = 0$ for all $i$'s and $j$'s.

If you say that each pair need to be distinct, then we can take $x_{N+i,j} = y_{N+i,j} = \epsilon_{i}$ to make each pair distinct, where $\epsilon_{i} \ll 1$ is an arbitrarily very small quantity. We also replace $R$ by $R+\Sigma_i \epsilon_i$.

• It is a little bit different from KNAPSACK, as we have to pick one and only one item from each set. Am I right? – Farzad Mar 4 '16 at 11:24
• No, this is exactly knapsack. Each set represents an item, which you can either pick or not. These are the two "items" that you select from the set. – Yuval Filmus Mar 4 '16 at 12:26

As Shreesh mentioned, you can reduce 0-1 knapsack to this problem in this way: In each set, only keep the (0, 0) pair and the pair with the most y to x ratio. the (0, 0) corresponds to setting $x_i$ in knapsack to be zero. Considering that each $y_i$ corresponds to $w_i$ in knapsack, and considering each $x_i$ in your problem as $v_i$ in knapsack, by setting $R$ as $(\displaystyle\sum_{j=1...N}y_j\ )- W$, you can solve knapsack by solving this problem and giving the opposite answer as the answer to 0-1 knapsack.