Q3. [30] Fractional Knapsack Problem An edited book has 6 articles. The table sh
ID: 3606790 • Letter: Q
Question
Q3. [30] Fractional Knapsack Problem An edited book has 6 articles. The table shows the lengths of the articles and their importance where the scale of importance is 1(low) to 10(high). The book must be at most 150 pages long The problem is to edit the book so that the overall importance is maximized. 1. [20] Edit the book by choosing articles whose pages and importance are given in the table. i.e Give A. [8] the list of the chosen articles with their chosen number of pages in the order B. C. [6] the importance for each chosen article and [6] the total maximum importance of the edited book. Article Importance of article Pages 15 20 10 30 4 4 2. [10] Consider a greedy rule for the above Fractional Knapsack Problem that selects the articles in non-decreasing order of pages. If the capacity of the knapsack is not exceeded, we take all of the pages. Otherwise, we take whatever portion of the article fills the knapsack and stop. Give an example to show that this greedy algorithm does not necessarily maximize the importanceExplanation / Answer
Answering only Q1 as multiple questions are asked
Calculating the fractional weightage of each article by w = pages * importance
A 45
B 100
C 40
D 90
E 240
F 240
Now, ordering according to weights, the articles must be edited in the following order - F, E, B, D, A, C
The importance of each article is as mentioned in the table above.
The maximum importance of the book is 240.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.