Question

there are 5 items as follows Items wi vi Item1 5 pounds 30$ Item2 10 pounds 20$ Item3 20 pounds 100$ Item4 30 pounds 90$ Item5 40 pounds 160$ The knapsack can hold 60 pounds find the optimal solution Select one: a. 250$ b. 290$ c. 270 $ d. 260 $

Answer 1

Answer:

Th correct answer of this question is 290$.

Step-by-step explanation:

Given - There are 5 items which are Item1 5 pounds 30$ Item2 10 pounds 20$ Item3 20 pounds 100$ Item4 30 pounds 90$ Item5 40 pounds 160$.

To Find - Find the optimal solution for the knapsack that can hold 60 pounds.

Item 1 wi is  5 pounds and vi is 30$

Item 2 wi is  10 pounds and vi is 20$

Item 3 wi is  20 pounds and vi is 100$

Item 4 wi is  30 pounds and vi is 90$

Item 5 wi is  40 pounds and vi is 160$

Item 6 wi is  60 pounds and vi is 290$

The knapsack can hold 60 pounds and the optimal solution is 290$

#SPJ1

Answer 2

Answer: The optimal solution is 260$

Step-by-step explanation:

Items              Wi                   Vi

Item1         5 pounds            30$

Item2       10 pounds           20$

Item3       20 pounds          100$

Item4       30 pounds           90$

Item5       40 pounds          160$

Let the number of items of Item1 be a, Item2 be b, Item3 be c, Item4 be d, Item5 be e

Net weight (in pounds)  = 5a + 10b + 20c + 30d + 40e

Net value (in dollars) = 30a + 20b + 100c + 90d + 160e

Optimal solution ⇒ Maximize net value

Max (30a + 20b + 100c + 90d + 160e)

Constrains :

• 5a + 10b + 20c + 30d + 40e  = 60 ( Net weight = 60 pounds)

• a, b, c, d and e = {0,1}  ( We can take an item or not take it )

e can't be more than 1 because , if e > 1 weight will become 80 pounds alone of Item 5

Case 1 : e = 1

5a + 10b + 20c + 30d = 20

d has to zero otherwise a, b or c will become negative

d = 0

5a + 10b + 20c = 20  

Subcase (i) of case 1 : c = 1

a = b =0

c =1

d = 0

e = 1

Net value = 30a + 20b + 100c + 90d + 160e

Net value = 0 + 0 + 100 + 0 + 160 = 260

Subcase (ii) of case 1 : c = 0

5a + 10b  = 20  

Possible ordered pairs  ( a, b ) : ( 4,0) , (2,1) , (0,2)

c =0

d = 0

e = 1

No feasible cases as a and b can't take values more than 1

Case 2 : e = 0

5a + 10b + 20c + 30d = 60  

Subcase (i) of case 1 : d = 1

5a + 10b + 20c = 30

a + 2b + 4c = 6

Possible ordered triplets  ( a, b, c) : ( 6,0,0) , (4,1,0) , (2,2,0), (2,0,1) , (0,1,1)

Feasible case : ( a, b, c) = (0,1,1)

d = 1

e = 0

Net value = 30a + 20b + 100c + 90d + 160e

Net value =  0 + 20 + 100 + 90 + 0 = 210

Subcase (ii) of case 1 : d = 0

5a + 10b + 20c = 60

a + 2b + 4c = 12

As a , b , c can only take values 0 and 1, maximum value of a+2b+4c = 8

Hence, no feasible case

Possible values = 260 and 210

Optimal solution = 260$

#SPJ3