Difference between revisions of "10.11"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
(Created page with "Answer to both a) and b) is no. Knapsack problem is NP-complete. ---- (a) Yes, this is a special case of the Knapsack problem where the value of each item is the same (desc...")
 
(Created page with "Answer to both a) and b) is no. Knapsack problem is NP-complete. ---- (a) Yes, this is a special case of the Knapsack problem where the value of each item is the same (desc...")
 
(No difference)

Latest revision as of 01:17, 21 September 2020

Answer to both a) and b) is no. Knapsack problem is NP-complete.



(a) Yes, this is a special case of the Knapsack problem where the value of each item is the same (described in section 13.10 of the book). If we have n programmes with sizes s1 to sn, where si <= sj if i < j, and we can fit the first k on the disk, there can be no larger subset, since in order to fit the (k+1)th item we must remove at least one other item of smaller or equal size.

(a) No. Let D = 10, and P = { 5, 4, 2, 1, 1, 1 }.


Back to Chapter 10