Question

Consider the following items in the Knapsack Problem:

Item                weight             value            Knapsack capacity W = 9.

1                      3                   $6

2 4 $12

3                      2                  $10

4                      5                  $20

Determine the maximum value in the knapsack if we allow repetitions; i.e., if there are an unlimited number of each item so that more than one such item can be chosen.

Find the missing value in the following linear array. P(w) is the maximum profit obtainable for a knapsack of capacity w.

w-->

            0       1      2       3       4       5       6       7       8       9

P(w):    0 0 10 10     20     20     30    30 40 ?  

P(9) =

Select one:

a. $38

b. $43

c. $32

d. $40

Answer 1

Solution:-

Given that:-

We need to find the maximum profit attainable for a Knapsack of capacity  

W = 9 p(9)

Determine the maximum value in the knapsack if we allow repetitions; i.e., if there are an unlimited number of each item so that more than one such item can be chosen.

we can use each item more than once as there is unlimited amount of each item.

We will solve this problem using dynamic programming considering capacity = 9

v[i, j] 0 1 2 3 4 5 6 7 8 9

0 0 0 0 0 0 0 0 0 0 0

3 0 0 0 3 3 3 6 6 6 9

4 0 0 0 3 12 12 12 15 24 24

2 0 0 10  10 20 20 30 30 40 40

5 0 0 0 3 20 20 30 30 40 40

weights

Find the missing value in the following linear array. P(w) is the maximum profit obtainable for a knapsack of capacity w.

Formula used

maximum profit = $ 40

when capacity = 9 in either of the 2 ways, filling bag with 1 item of weight 5 and 2 items of weight 2.

OR by filling bag with 4 items of weight 2

correct answer = $ 40. option "d".

Thanks for supporting...

Please give positive rating....