Talk:Knapsack problem/Unbounded: Difference between revisions

Content added Content deleted

Inline

Revision as of 07:04, 3 December 2008

Dynamic Python solution

Is the underlying algorithm so different from what I called an exhaustive search solution? I don't think so. P.S: should the line w = sack.volume; v = sack.volume have the first volume replaced by weight?

It's great that you thought the problem worthy of your time though. I spent ages trying to find something beginning with K and then on formulating the problem :-)

--Paddy3118 05:40, 3 December 2008 (UTC)

Yes, in theory. Dynamic programming runs in time polynomial in the size of the sack weight, sack volume, and number of types of items; whereas the exhaustive search runs in time exponential in the number of types of items. But since the number of types of items here is so small (3), you won't see much of a difference. --Spoon! 07:04, 3 December 2008 (UTC)

Revision as of 05:40, 3 December 2008 (view source) rosettacode>Paddy3118 (Dynamic quite similar algorithm wise to exhaustive?)		Revision as of 07:04, 3 December 2008 (view source) rosettacode>Spoon! No edit summary Newer edit →
Line 6:		Line 6:

	--[[User:Paddy3118\|Paddy3118]] 05:40, 3 December 2008 (UTC)		--[[User:Paddy3118\|Paddy3118]] 05:40, 3 December 2008 (UTC)

			:Yes, in theory. Dynamic programming runs in time polynomial in the size of the sack weight, sack volume, and number of types of items; whereas the exhaustive search runs in time exponential in the number of types of items. But since the number of types of items here is so small (3), you won't see much of a difference. --[[User:Spoon!\|Spoon!]] 07:04, 3 December 2008 (UTC)