1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted