Difference between revisions of "TADM2E 8.5"

From Algorithm Wiki
Jump to: navigation, search
(Replaced content with "Sujanqgehd")
(Undo revision 1068 by FuckMatt (talk))
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Sujanqgehd
+
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 }.

Latest revision as of 00:59, 1 August 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 }.