0-1 kNapsack problem FPTAS algorithm

  • Thread starter Thread starter StIgM@
  • Start date Start date
  • Tags Tags
    Algorithm
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

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:
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.
 
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
Thread 'Imaginary Pythagorus'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top