Anonymous user
Talk:Knapsack problem/Unbounded: Difference between revisions
no edit summary
(→Dynamic Python solution: Exponential?) |
No edit summary |
||
Line 10:
:: I'm new to this big-O notation stuff, but I think my algorithm would run in time proportional to: <pre>the product of ( the minimum of ( max_restriction(r)/restriction(r of i) for all restrictions r ) ) for each item i </pre> I can't see the exponential? --[[User:Paddy3118|Paddy3118]] 07:44, 3 December 2008 (UTC)
::: Let n = the number of types of items. So what I am saying is that you are taking the product of n things. So as n grows, you can think of it as something like (something)^n in the worst case. Or in other words, every time you add a new type of item, you always have to multiply it by some (potentially big) number. With the dynamic programming solution, it runs in time of (something)*n; so when n is already very big, adding a new type of item does not increase it by very much. Perhaps you can experiment with this and see what happens if you add a whole bunch of new items. --[[User:Spoon!|Spoon!]] 10:01, 3 December 2008 (UTC)
| |||