TADM2E 8.5 - Revision history

Matt: Undo revision 1068 by FuckMatt (talk)

2020-08-01T00:59:39Z

Undo revision 1068 by FuckMatt (talk)

2020-07-31T09:39:08Z

Blanked the page

2020-07-23T14:39:41Z

Undo revision 777 by FuckYou (talk)

2020-07-14T01:43:00Z

Replaced content with "Sujanqgehd"

2016-12-20T18:21:04Z

2016-10-14T22:42:28Z

Created page with "Answer to both a) and b) is no. Knapsack problem is NP-complete."

New page

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

← Older revision	Revision as of 00:59, 1 August 2020
Line 1:	Line 1:
	+	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 }.

← Older revision		Revision as of 09:39, 31 July 2020
Line 1:		Line 1:
−	~~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 }.~~

← Older revision		Revision as of 14:39, 23 July 2020
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 }.

← Older revision		Revision as of 01:43, 14 July 2020
Line 1:		Line 1:
−	~~Answer to both a) and b) is no. Knapsack problem is NP-complete.~~	+	Sujanqgehd
−
−	~~----~~
−
−
−	(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 }.~~

← Older revision		Revision as of 18:21, 20 December 2016
Line 1:		Line 1:
	Answer to both a) and b) is no. Knapsack problem is NP-complete.		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 }.