Question

In a 0/1 Knapsack problem implemented using dynamic

programming, a common mistake is to allow items to be reused, effectively turning it into an unbounded knapsack. Which part of the recurrence relation, if incorrectly formulated, would lead to this bug?

A dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i]] + values[i])

B dp[i][j] = max(dp[i-1][j], dp[i][j - weights[i]] + values[i])

C dp[i][j] = dp[i-1][j]

D dp[i][j] = dp[i][j - weights[i]] + values[i]

E dp[i][j] = values[i]

Practice Next

More IT Operating System Questions

Which of the following books is NOT mandated to be maintained under the Companies Act, 2013?
In fund flow analysis, which of the following is considered a source of funds?
In a manufacturing entity, the cost of abnormal waste is:
A firm has EBIT of ₹10 lakh, tax rate 30%, cost of equity 15%, and cost of debt 10%. It has 50% debt and 50% equity. Calculate WACC (assuming book val...
Accounting Standard 2 (Revised) provides the _______ method for computing the cost of inventories.
Unclaimed dividend is shown in the balance sheet under the head
When was the PM E-DRIVE scheme initially launched?
Economic life of an enterprise is split into the periodic interval as per which concept?
The Coir Board is primarily responsible for the development of which sector?
ICDS IV primarily deals with which aspect of financial reporting

In a 0/1 Knapsack problem implemented using dynamic

Solution