Question

ection 3 of 6 Algorithm
Question #4
Revisit
What is the maximum profit earned in the following situation, while solving through the 0/1
knapsack using dynamic programming, if the maximum capacity of the bag is 15?
Obj
1 2 3 4 5
Profit 60 15 30 80 20
Weight 5 2
16
10 8​

Answer 1

Answer:

this is the correct answer

Answer 2

The maximum profit earned in the given situation is 140

Given,

Object = {1, 2, 3, 4, 5}

Profit = {60, 15, 30, 80, 20}

Weight = {5, 2, 16, 10, 8}

The maximum capacity of the bag is 15

To Find,

The maximum profit earned in the situation given above

Solution,

We are advised to use a 0/1 knapsack using dynamic programming to solve this question

Dynamic programming is used when a problem breaks down into recurring small subproblems. The algorithm finds solutions to subproblems and stores them in memory for later use

Knapsack problem: pack the given items into a back such that the profit is maximum and the total weight does not exceed the maximum capacity of the bag

0/1 knapsack problem is the kind of knapsack problem where an item is either selected in its entire quantity or the item is not selected at all. This means that a fraction of one item cannot be selected; if an item is selected, its entire weight should be selected

So here, we have 32 [$2^ n = 2^5$ ] possibilities of arrangement into the bag

We have to maximize the profit in such a way that total weight is less than 15

Therefore, the objects 4 and 1 are selected which have weights of 5 ad 10 respectively which adds up to a total of 15. The profit, in this case, is maximum, and the maximum profit 60 + 80 = 140