(adsbygoogle = window.adsbygoogle || []).push({}); 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

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!

# Homework Help: Knapsack problem constraints help

Have something to add?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**