tag:blogger.com,1999:blog-11149365.post5437317569960489333..comments2024-03-23T04:34:59.089+00:00Comments on Go deh!: XKCD Knapsack SolutionPaddy3118http://www.blogger.com/profile/06899509753521482267noreply@blogger.comBlogger31125tag:blogger.com,1999:blog-11149365.post-85947477286007368172009-06-21T08:15:31.179+01:002009-06-21T08:15:31.179+01:00Appetizers is a heading. Sandwiches is a heading. ...Appetizers is a heading. Sandwiches is a heading. Sandwiches are not part of Appetizers. A sampler plate is a mixture of the aforementioned appetizers. The indentation argument is irrelevant since it is on an angle and is hand drawn - you might as well argue side salad is indented because the artist drew a lump on the paper at that point.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-28705812609496830292009-06-21T05:53:11.871+01:002009-06-21T05:53:11.871+01:00To that Anon. who knows how to spell barbecue: tha...To that Anon. who knows how to spell barbecue: thank you. It's appreciated, although I probably won't fix the post due to the clunky Blogger HTML editor that seems to have a, (warped), mind of its own.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-39531786322145885502009-06-20T19:17:29.868+01:002009-06-20T19:17:29.868+01:00In case you care, it's barbecue, not barbeque....In case you care, it's barbecue, not barbeque.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-73898406934102058132009-06-20T09:54:48.662+01:002009-06-20T09:54:48.662+01:00Hi Bowerbird,
Stay happy :-)Hi Bowerbird,<br /><br />Stay happy :-)Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-82374261041845153012009-06-19T20:35:58.124+01:002009-06-19T20:35:58.124+01:00i love the elegance of brute force... :+)...i love the elegance of brute force... :+)<br /><br />far better than getting bogged down<br />in unfunny programming discussions.<br /><br />-bowerbirdbowerbirdhttps://www.blogger.com/profile/05962115094107919533noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-24883754417351220712009-06-19T18:13:14.717+01:002009-06-19T18:13:14.717+01:00I think you should have set aside at least 15% for...I think you should have set aside at least 15% for tip. Leaving only $12.79 for food items. Poor waiter.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-57893817018297501442009-06-19T18:03:46.461+01:002009-06-19T18:03:46.461+01:00Half-cent fairy dust. A sprinkle here, a sprinkle ...Half-cent fairy dust. A sprinkle here, a sprinkle there, pretty soon your talkin' real mony.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-27931746420117634882009-06-16T22:29:52.516+01:002009-06-16T22:29:52.516+01:00Oh, I forgot to change the target price back to 15...Oh, I forgot to change the target price back to 1505 (change 523515 to that in the last line).<br /><br />The knapsack problem is interested in any solution (that is, it will find any that maximizes value for items that can fit inside the knapsack). In other words, it returns one solution that works.dynamic programming guynoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-36515928420109107102009-06-16T22:11:49.113+01:002009-06-16T22:11:49.113+01:00Hi DP Guy,
I ran your amendment code on the link y...Hi DP Guy,<br />I ran your amendment code on the link you gave.<br /><br />It returned a list of 7 instances of the string 'FRENCH FRIES' followed by 2426 instances of 'MIXED FRUIT'.<br /><br />Your original snippet does the same.<br /><br />I didn't understand your last comment. surely any solution that works would be the same as all solutions?<br /><br />- Paddy.<br /><br />P.S: Python 2.6.1Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-67574440232728380382009-06-16T00:15:16.506+01:002009-06-16T00:15:16.506+01:00PS, it doesn't yield all solutions; just any t...PS, it doesn't yield all solutions; just any that work. Finding all solutions would certainly complicate the code.dynamic programming guynoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-70662195188432855372009-06-16T00:06:34.701+01:002009-06-16T00:06:34.701+01:00Here's my solution, Paddy:
http://pastebin.com...Here's my solution, Paddy:<br />http://pastebin.com/m3c71247b<br /><br />The execution times for the given problem are almost identical. However, if you bump up the target price to say, $220, the differences are quite notable. <br /><br />I probably could wheedle some more optimization out of it: the most obvious one is to divide the weights (meal prices) and the target (knapsack capacity) by their GCD to reduce the size of the arrays and I'm sure there are some more non-obvious ones a smarter person could find. I wasn't positive on the best way to force it to get exactly the price in question, so my method of doing that might have been suboptimal.<br /><br />Note that this is about 25 or so minutes of work, so I may have one or two bugs, but it seems to work well.<br /><br />I don't do well with commenting on code, but if you have a question, ask and I'll do my best to explain.dynamic programming guynoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-56155816676055465912009-06-15T18:27:16.792+01:002009-06-15T18:27:16.792+01:00@Anon, (the one going on about dynamic programming...@Anon, (the one going on about dynamic programming), drone, drone, drone. Show me the code!<br /><br />I penned a useful (true) knapsack problem elsewhere on my blog that is also on Rosetta Code. <br /><br />Check out the <a href="http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming" rel="nofollow">WP entry for dynamic programming</a> and state where the optimal substructure, and overlapping subproblems lay for example.<br /><br />As for training and big-O notation and scalability, it is easy to say. Try and apply DP and see how far you get. I doubt you can do better than this, or my second, <a href="http://paddy3118.blogspot.com/2009/06/xkcd-simpler-knapsack-solution.html" rel="nofollow">simpler version</a> in terms of big-O. but I would be enriched if you could, so please try.<br /><br />- Paddy.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-76030364237855966462009-06-15T15:22:43.703+01:002009-06-15T15:22:43.703+01:00@Anon: Your post is irrelevant, Paddy already decl...@Anon: Your post is irrelevant, Paddy already declared his solution as a bruteforce one. Other than that his programme solved the given problem. You might be very clever, but seriously lack the sense for fun.ähm...https://www.blogger.com/profile/13959914796579158605noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-33394996972463804102009-06-15T15:08:19.493+01:002009-06-15T15:08:19.493+01:00Paddy, you clearly have very little training with ...Paddy, you clearly have very little training with algorithms. Do you know what big-O notation is?<br /><br />Dynamic programming reduces the solution time from exponential to pseudopolynomial. Why is this important? Neither of your solutions scale well. Many "real-world" applications of the knapsack problem, some of which appear in the world of cryptography. In these cases, you'll have far more than 6 items. You might also run into a case where each item has an associated value, and you want to maximize it while staying under the weight (which, incidentally, is how the original knapsack problem is worded).<br /><br />Point being, your solution will not be very useful in any other case other than this.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-15305620681242266522009-06-15T07:36:42.406+01:002009-06-15T07:36:42.406+01:00See my next blog entry for a better solution. I us...See my <a href="http://paddy3118.blogspot.com/2009/06/xkcd-simpler-knapsack-solution.html" rel="nofollow">next blog entry</a> for a better solution. I use plain recursion and integers, but keep the sandwich. (It makes my solutions stand out from the crowd).<br /><br />P.S. @Anon: "More than one restaurant...", So you admit we agree on one :-)<br /><br />P.P.S. @ruiaf and others: Dynamic programming is a nice name, but I don't get its applicability after reading the Wikipedia entry? If you do a DP solution then please link to it here.<br /><br />- Paddy.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-27985836331242540742009-06-15T00:54:54.771+01:002009-06-15T00:54:54.771+01:00Go for the dynamic programming solution.Go for the dynamic programming solution.Anonymoushttps://www.blogger.com/profile/09314928777349758472noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-73061534900211159552009-06-15T00:14:15.388+01:002009-06-15T00:14:15.388+01:00If you can show me more than one restaurant that i...If you can show me more than one restaurant that includes a list of sandwiches in the appetizer section, I'll eat my hat.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-77854530000109642292009-06-14T22:37:26.242+01:002009-06-14T22:37:26.242+01:00...Or use rationals, or use decimals.
- Paddy....Or use <a href="http://docs.python.org/library/fractions.html?highlight=rationals" rel="nofollow">rationals</a>, or use <a href="http://docs.python.org/library/decimal.html?highlight=decimals" rel="nofollow">decimals</a>.<br /><br />- Paddy.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-42287287497113969542009-06-14T21:26:37.679+01:002009-06-14T21:26:37.679+01:00You could express all the values in cents instead ...You could express all the values in cents instead of dollars. That way, all they values would be integers and you wouldn't need to worry about floating-point rounding errors.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-90161473678226732972009-06-14T18:47:22.416+01:002009-06-14T18:47:22.416+01:00Any chance of an expanded version explaining all t...Any chance of an expanded version explaining all that? I'm feeling thick ATM ;)Orestis Markouhttp://orestis.grnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-67630908933254773752009-06-14T17:04:46.959+01:002009-06-14T17:04:46.959+01:00actually paying the bill is the same problem.actually paying the bill is the same problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-32691801727843674972009-06-14T15:45:33.687+01:002009-06-14T15:45:33.687+01:00... Then xkcd shouldn't indent the sandwiches ...... Then xkcd shouldn't indent the sandwiches under appetizers!Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-14125338474407428892009-06-14T12:16:59.041+01:002009-06-14T12:16:59.041+01:00"Assuming the one sandwich represents the end..."Assuming the one sandwich represents the end of the menu" methinks you need to brush up on your reading skills. The $15.05 of food is explicitly stated to come from the list of APPETIZERS, not APPETIZERS AND ONE SANDWICH.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-9986979552424675152009-06-14T11:06:50.230+01:002009-06-14T11:06:50.230+01:00I don't know, just looking at the cartoon and ...I don't know, just looking at the cartoon and the menu it took me approx. 15 seconds to realize that I could do it with giving them all Fresh Fruit, since the order did not specify a mix of appetizers that is exactly what I would do.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-75820050159745026572009-06-14T09:04:43.507+01:002009-06-14T09:04:43.507+01:00You leave my mother out of this!
You will note ho...You leave my mother out of this!<br /><br />You will note however the gentle sprinkling of 'int' and half cent fairy dust to appease the floating point approximation gods.<br /><br />- Paddy.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.com