# 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?

Thanks in advance

Note: It's not homework. The problem is different and this example is a simplification.

Last edited: Sep 24, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted