2
$\begingroup$

Consider the following problem:

We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-size knapsacks. A feasible solution is an $m$-tuple $U=\{U_1,...,U_m\}$, such that the size of items in each knapsack doesn't exceed its capacity, and each item is packed in no more than one knapsack. more formally:

  • for every $j, 1 \le j \le m, U_j \subseteq I$ and $ \sum_{i \in U_j}s_i \le 1$
  • for every $j,l, 1 \le j < l \le m, U_j \cap U_l = \phi $

the profit of the feasible solution is $ \sum_{j=1}^m\sum_{i \in U_j}p_i $. The goal is to find a feasible solution of maximal profit.

I'm trying to show a PTAS for the problem.

It was suggested to use linear programming. I thought about the following (basic) linear program:

maximise $ \sum_{j=1}^m\sum_{i=1}^n x_{ij}p_i $

under the constraints:

  • for every $ 1 \le j \le m \sum_{i=1}^n s_ix_{ij} \le 1 $ (the size of items in each knapsack doesn't exceed its capacity)
  • for every $ 1 \le j \le n \sum_{j=1}^m x_{ij} \le 1 $ (each item is packed in no more than one knapsack).

I don't know how to proceed from here. I'm not sure how to develop an algorithm (choose in which knapsack to put each item) based on this linear program. Can anyone pls give me a clue?

Thanks.

$\endgroup$
  • $\begingroup$ This is commonly known as bin packing.. $\endgroup$ – vonbrand Feb 23 at 19:25
  • $\begingroup$ Thanks! Iv'e tried to search for it, but I can't find an answer for the problem when there is a fixed number of knapsacks/bins, and the general case is much more complicated. If you can find an answer to the special problem I would really appreciate it. $\endgroup$ – Tav Feb 24 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.