Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

0-1 kNapsack problem FPTAS algorithm

  1. Sep 24, 2014 #1
    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: Sep 24, 2014
  2. jcsd
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

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