Directions (Q91–95): For a knapsack problem, P and W are the profits and weights of a set of 7 items:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}
Which of the following statements about the knapsack problem is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. In the 0/1 knapsack problem items cannot be divided into smaller portions, while in the fractional knapsack items can be divided in any proportion.
Explanation
That is the defining difference. (Greedy is used for the fractional version and DP for 0/1, the reverse of option C.)More Data Structures and Algorithms questions
- How many different binary trees are possible with n nodes?
- Let n denote a positive integer. A function f is defined as f(n) = 0, if n = 1 f(n) = f(⌊n/2⌋) + 1, if n > 1 What is f(25), and what does t…
- Given the FFT, we can have a ______ time procedure for multiplying two polynomials A(x) and B(x) of degree bound n, where input and output…
- Circuit satisfiability problem: given a Boolean combinational circuit composed of AND, OR and NOT gates, is it satisfiable? A one-output Bo…
- Given the expression (A + B * D) / (E − F) + G: 1. The prefix notation is + / + A * D B − E F G 2. The prefix expression is the reverse of…
- Match List I with List II. Choose the correct answer from the options given below:List I List II a. Dijkstra's algorithm I. Calculates path…