Hi anyone can help me to solve this Discrete Math Problem Th

Hi anyone can help me to solve this Discrete Math Problem? Thank you so much.

Consider the following instance of the Knapsack Problem with n = 7 and B = 10 Use some enumerative approach to find the optimal set. Find the optimal value using the Dynamic Programming approach. Show your backtracking to find which items to put into the knapsack. Prove the following: If S

Solution

1)

a)

Enumerative problem solution

maximum values we can get 17
Susbet is 1 2 5

b)

Maximum value is 17

subset is 5 2 1

2)

Proving is quite easy. If you increase the basket size, it means B here then we not only can accomodate those previous items we did but we might accomodate new one or we can choose some other item whose value is more than some either item we had in basket. Suppose new B is 12 then instead of choosing 1 2 and 5 , we chose 2, 3, 6 which will give us now 22 value.

3) Same here if we increase n and add some 1 size item with bigger value it might increase our value.

Hope this Helps!!