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}
What is the maximum value of the items you can carry if the maximum weight allowed is 25 (fractional knapsack)?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. 48.1
Explanation
Continuing past capacity 15 (profit 40), add item2 (w 5, p 5): weight 20, profit 45. Then 5/11 of item4: 5/11 × 7 ≈ 3.18. Total ≈ 48.18.More Data Structures and Algorithms questions
- If a new item (P = 5, W = 2) is added, giving 8 items, and the capacity is 25, then the time of fractional knapsack in this case is ______
- The most efficient solution to the fractional knapsack problem with maximum capacity 15 is obtained using ___
- 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…