I have the following 0-1 knapsack problem variant:(adsbygoogle = window.adsbygoogle || []).push({});

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

- farmer 1: a_{11}units at cost c_{11}, ..., a_{1n1}units at cost c_{1n1}

.........

- farmer m: a_{m1}units at cost c_{m1}, ..., a_{mnm}units at cost c_{mnm}

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.

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# 0-1 kNapsack problem FPTAS algorithm

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - kNapsack problem FPTAS | Date |
---|---|

I A problem in combinatorics | Jan 17, 2018 |

B Optimisation problem | Jan 11, 2018 |

I Math papers and open problems | Dec 11, 2017 |

**Physics Forums - The Fusion of Science and Community**