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!

Knapsack problem constraints help

  1. Nov 12, 2017 #1
    1. The problem statement, all variables and given/known data
    8 (a) (The Knapsack Problem) A backpacker's knapsack has a volume of V in.^3 and can hold up to W lb of gear. The backpacker has a choice of ##n## items to carry in it, with the ##i##th item requiring ##a_i## in.^3 of space, weighing ##w_i## lb, and providing ##c_i## units of value for the trip. What items should be taken in the knapsack?

    (b) Refine part (a) to include the following considerations: Item 1, a can of tuna fish, Item 2, a can of corn, and Item 3, a can of stew, have no value unless Item 4 the can opener, is taken; and only one snack, either Item 5, potato chips, or Item 6, unpopped popcorn, is to go. Of course Items 2,3, and 6 all use Item 7, the cooking pot.
    2. Relevant equations


    3. The attempt at a solution
    Let ##x_i = 1## if item i is brought, and ##x_i = 0## if item i is not brought.

    a)

    Maximize ##c_1x_1 + c_2x_2 + . . . + c_nx_n##
    subject to
    ##a_1x_1 + a_2x_2 + . . . + a_nx_n \le V##
    ##w_1x_1 + w_2x_2 + . . . + w_nx_n \le W##
    ##0 \le x_i \le 1## and ##x_i## is integral.
    ##c_i, a_i, w_i \ge 0##
    b)

    Maximize ##c_1x_1 + c_2x_2 + . . . + c_nx_n##
    subject to
    ##a_1x_1 + a_2x_2 + . . . + a_nx_n \le V##
    ##w_1x_1 + w_2x_2 + . . . + w_nx_n \le W##
    ##c_1 + c_2 + c_3 = (c_1 + c_2 + c_3)x_4## (if item 4 is not brought, then these c's should have 0 value)
    ##x_5 + x_6 \le 1##
    ##x_2 + x_3 + x_6 \le 3x_7## (if item 7 is not brought, then none of these items are brought)

    ##0 \le x_i \le 1##, ##x_i## is integral.
    ##c_i, a_i, w_i \ge 0##

    My question is, for part b are my constraints correct?
     
    Last edited: Nov 12, 2017
  2. jcsd
  3. Nov 12, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That equation is only true if ##x_4=1 ##or ##c_1 + c_2 + c_3 = 0##. The ##c_i## are given constants and you can't expect them to be zero. Your equation forces you to take the can opener.
    You can use the same approach as for the cooking pot here, for the maximization there is no point in bringing worthless items anyway.
    Technically you don't know that. It is also not necessary to specify as these values are given anyway.
     
  4. Nov 12, 2017 #3

    scottdave

    User Avatar
    Homework Helper
    Gold Member

    It is not clear to me from your statement if more than 1 of each item can be brought. Where do you get the list of values and weights and volumes?
     
  5. Nov 12, 2017 #4
    I think if say.. I brought 2 identical toothbrushes, then they would just count as 2 separate items with the same weight/volume/value. In total we get ##n## items, but I don't think they have to be unique. The values/weights/volumes aren't specified.
     
  6. Nov 12, 2017 #5
    Ok so the constraint would be ##x_1 + x_2 + x_3 \le 3x_4## This means if we don't bring the can opener, then ##x_4 = 0##. Therefore ##x_1, x_2, x_3 = 0##. I was hesitant to use this because I thought there would be cases where we brought the unopennable items without the can opener, so their value would be 0, but we'd still have to account for their weight/volume. But I see from your comment, that would be redundant so we don't need to consider that.
     
  7. Nov 12, 2017 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Ah...there is a better option. You can express the value of item 1 using c1 and x4. Then you can bring 1 without 4, but it has zero value - exactly as the problem statement wants.
     
  8. Nov 12, 2017 #7
    That would mean changing the objective function to
    Maximize ##x_4x_1c_1 + x_4x_2c_2 + x_4x_3c_3 + x_4c_4 + x_5c_5 + . . . + x_nc_n##
     
  9. Nov 12, 2017 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Right.
     
  10. Nov 12, 2017 #9

    StoneTemplePython

    User Avatar
    Gold Member

    This is a quadratic program over an integer domain. Solvers exist for this (e.g. Gurobi) but this is considerably more advanced than even a linear program over an integer domain. Are you sure you want to model it this way?
     
  11. Nov 12, 2017 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    OP is not supposed to find a solution to an actual problem anyway.
     
  12. Nov 13, 2017 #11

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Just as a matter of form: do not include the statement ##c_i, a_i, w_i \ge 0## within the scope of the model input itself: doing so makes it look like you are regarding the ##c_i##, ##a_i## and ##w_i## as additional variables in the optimization. In fact, they are not "variables" at all; they are given as input data supplied from outside the model itself.

    Next: your constraint ##x_5 + x_6 \le 1## allows both ##x_5 = 0## and ##x_6 = 0##, which is perfectly OK if your interpretation is that you can have at most one snack. If you must include exactly one snack, replace that constraint by ##x_5 + x_6 = 1##.

    Finally, in some books and papers the constraint "##0 \le x_i \le 1##, ##x_i## is integral" would be simply "##x_i = 0,1##" or "##x_i## binary" (and, of course, you should specify that it holds for all ##i##).
     
  13. Nov 13, 2017 #12
    This all makes sense, ill keep it in mind on the rest of this chapter. Also i'll probably make a note next to the constraint to clarify that I think we can bring at most one snack. Thank you.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Knapsack problem constraints help
  1. Help with basic problem? (Replies: 15)

  2. Help with Word Problem (Replies: 2)

Loading...