An edited book has 6 articles. The table shows the lengths of the articles and t
ID: 3806942 • Letter: A
Question
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.
**So I thought The answer to A was to add them up in order of highest importance to lowest importance and that would give us the correct answer [C+F+D+A+E for 145 pages with importance of 21] . I was told this was wrong and given the hint that we have to use fractions. My second thought was essentially the same thing but to use a fraction of B as well [C+F+D+A+E+0.1B for 150 pages with importance of 21.3]. I was told this is also wrong. Why is that and what is the correct answer?
Article Pages Importance
A) Edit the book by choosing articles whose pages and importance are given in the above table. Show all your work and how you determined the answer. i.e. Give
I) the chosen articles with its pages,
II) the importance for each chosen article and
II) the total maximum importance of the edited book.
B) 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 importance.
Article Pages Importance A 20 2 B 50 3 C 60 8 D 15 4 E 20 1 F 30 6Explanation / Answer
A) The idea is to use fractional knapsack only but to add the pages in the order of highest importance per page.
We calculate importance per page.
Article Pages Importance
Article
Pages
Importance
Importance per page
Importance per page *
LCM of pages(multiplied with LCM just to make it a whole number)
Importance Per page
A
20
2
2/20
2*900/20
90
B
50
3
3/50
3*900/50
54
C
60
8
8/60
8*900/60
120
D
15
4
4/15
4*900/15
240
E
20
1
1/20
1*900/20
45
F
30
6
6/30
6*900/30
180
Pages are selected in the order of highest importance per page. If capacity is there, whole Book is included otherwise fraction of book is included.
As per the above calculation, Order of highest importance per page is D,F,C,A,B,E
so we pick D,F,C,A with sum total of 125 pages. and 25 pages of Book B.
Article
Pages
Importance
D
15
4
F
30
6
C
60
8
A
20
2
B
25
(3/50)*25 = 1.5
SUM TOTAL
150
21.5
This solution gives us maximum importance of 21.5.
B) If we select articles in increasing order of pages, we will add the Articles in following order.
Article
Pages
Importance
D
15
4
A
20
2
E
20
1
F
30
6
B
50
3
C
15
2
SUM TOTAL
150
18
This solution gives as maximum importance of 18 which is lesser than the solution we find previous part of problem.
Please let me know in case of any doubt.
Thanks
Article
Pages
Importance
Importance per page
Importance per page *
LCM of pages(multiplied with LCM just to make it a whole number)
Importance Per page
A
20
2
2/20
2*900/20
90
B
50
3
3/50
3*900/50
54
C
60
8
8/60
8*900/60
120
D
15
4
4/15
4*900/15
240
E
20
1
1/20
1*900/20
45
F
30
6
6/30
6*900/30
180
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.