# 0-1 kNapsack problem FPTAS algorithm

1. Sep 24, 2014

### StIgM@

I have the following 0-1 knapsack problem variant:

I want to buy X units of a product at min cost, and there are m farmers that offer:

- farmer 1: a11 units at cost c11, ..., a1n1 units at cost c1n1
.........
- farmer m: am1 units at cost cm1, ..., amnm units at cost cmnm

and I can choose at most one option from each farmer.

Formally, I want to

$$Minimise \sum_{i=1}^{m} \sum_{j=1}^{n_i} x_{ij}c_{ij}$$

subject to $$\sum_{i=1}^{m} \sum_{j=1}^{n_i} x_{ij}a_{ij} >= X$$

where $$x_{ij}\in\{0,1\}$$

Could you please let me know if this problem resembles a variant of 0-1 knapsack problem?

Is there any FPTAS algorithm that suits this problem?