Difference between pages "4.29" and "10.11"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with " Back to Chapter 4") |
(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...") |
||
| Line 1: | Line 1: | ||
| + | Answer to both a) and b) is no. Knapsack problem is NP-complete. | ||
| + | ---- | ||
| − | Back to [[Chapter | + | |
| + | (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]] | ||
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
