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.