- #1

- 334

- 44

## Homework Statement

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.

## Homework Equations

## 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: