- #1
StIgM@
- 8
- 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.
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: