0-1 kNapsack problem FPTAS algorithm

  • Context: Graduate 
  • Thread starter Thread starter StIgM@
  • Start date Start date
  • Tags Tags
    Algorithm
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 1K views
StIgM@
Messages
8
Reaction score
0
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

[tex]Minimise \sum_{i=1}^{m} \sum_{j=1}^{n_i} x_{ij}c_{ij}[/tex]

subject to [tex]\sum_{i=1}^{m} \sum_{j=1}^{n_i} x_{ij}a_{ij} >= X[/tex]

where [tex]x_{ij}\in\{0,1\}[/tex]

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:
Mathematics news on Phys.org
If you only can decide between "buy all" and "do not buy" from a certain farmer, then it is a 0-1-problem. It is an ordinary optimization problem, so algorithms like the simplex algorithm should help. The complexity of the problem is another question, i.e. whether it is NP complete or not. Looks as it is at first sight, but to decide this the problem has to be stated very precisely and a proof is needed.