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}
The most efficient solution to the fractional knapsack problem with maximum capacity 15 is obtained using ___
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. Greedy Algorithm
Explanation
Taking items in decreasing order of profit/weight ratio (greedy) is optimal for the fractional knapsack.More Data Structures and Algorithms questions
- Which of the following statements about the knapsack problem is correct?
- 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…