Anonymous user
Talk:Knapsack problem/Unbounded: Difference between revisions
m
→Dynamic Python solution: corrected misspelling of ''dynamic'' -- ~~~~
m (moved Talk:Knapsack problem to Talk:Knapsack problem/unbounded: This task is in point of fact the "unbounded knapsack problem" see the wikipedia! [http://en.wikipedia.org/wiki/Knapsack_problem]) |
m (→Dynamic Python solution: corrected misspelling of ''dynamic'' -- ~~~~) |
||
| (4 intermediate revisions by 4 users not shown) | |||
Line 17:
:The problem is that in order to use the dynamic programming solution I had to re-word the problem to only use integer weights and volumes. So the printout is correct for that problem statement. I guess I could manually divide the weights and volumes by the corresponding amounts when I print them, but it doesn't seem like a very nice solution. --[[User:Spoon!|Spoon!]] 22:59, 2 January 2009 (UTC)
::I found [[http://razvi.wordpress.com/2008/10/09/dynamic-programming-integer-knapsack/ this]] to help work out what the
:::Note however that that page addresses a slightly different problem; the "0-1" problem, where you can take at most 1 of each item. Whereas in the problem here we can take as many of each item as we want. --[[User:Spoon!|Spoon!]] 02:48, 6 January 2009 (UTC)
==The problem with the PARI/GP solution==
Is that it output includes non-optimal solutions, something like:
<pre>$ 30000 : 0 panecea, 0 ichor, 12 gold
$ 31800 : 0 panecea, 1 ichor, 12 gold
$ 33600 : 0 panecea, 2 ichor, 12 gold
$ 35400 : 0 panecea, 3 ichor, 12 gold
$ 37200 : 0 panecea, 4 ichor, 12 gold
$ 39000 : 0 panecea, 5 ichor, 12 gold
$ 40100 : 0 panecea, 7 ichor, 11 gold
$ 41900 : 0 panecea, 8 ichor, 11 gold
$ 43700 : 0 panecea, 9 ichor, 11 gold
$ 45500 : 0 panecea, 10 ichor, 11 gold
$ 47300 : 0 panecea, 11 ichor, 11 gold
$ 49100 : 0 panecea, 12 ichor, 11 gold
$ 50900 : 0 panecea, 13 ichor, 11 gold
$ 52700 : 0 panecea, 14 ichor, 11 gold
$ 54500 : 0 panecea, 15 ichor, 11 gold
$ 54500 : 3 panecea, 10 ichor, 11 gold
$ 54500 : 6 panecea, 5 ichor, 11 gold
$ 54500 : 9 panecea, 0 ichor, 11 gold</pre>
You need to go the extra mile and reduce the output to the ''very'' "best", as the task description requires. --[[User:Paddy3118|Paddy3118]] 06:59, 30 October 2010 (UTC)
== Terrible numbers ==
With the numbers given, dynamic programming didn't produce a single cache hit. Basically the given data is perfect for brute force, and a very easy one at that. Probably not worth all the discussions about big-O as is. --[[User:Ledrug|Ledrug]] 02:01, 11 June 2011 (UTC)
: "restructured. Still brute force (data makes caching not worthwhile), but at least it doesn't hard code three nested loops.)". ''At least'' what? Recursive and iterative methods are both ok (in this case). Maybe you meant to say "recursive brute force instead of iterative"? I even wonder how would you do three nested loops without hard-coding them. About discussions on big-O, '''actual''' examples do not matter, change the "terrible numbers" and make worth it. --[[User:ShinTakezou|ShinTakezou]] 19:35, 21 May 2012 (UTC)
| |||