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}
Find the optimal solution of the fractional knapsack problem when the maximum capacity is 15.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. 40
Explanation
Profit/weight ratios: item5 6, item1 4.5, item7 3, item6 1.78, item2 1, item4 0.64, item3 0.33. Take item5 (w 1, p 6), item1 (w 2, p 9) and item7 (w 3, p 9), total weight 6, profit 24. Then item6 (w 9, p 16) fills it exactly: weight 15, profit 40.More Data Structures and Algorithms questions
- What is the maximum value of the items you can carry if the maximum weight allowed is 25 (fractional knapsack)?
- 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…