Editing Talk:287: NP-Complete
![]() |
Please sign your posts with ~~~~ |
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
− | |||
Shame this only works in restaurants that price all their appetizers differently. [[User:Davidy22|Davidy22]] ([[User talk:Davidy22|talk]]) 03:18, 13 October 2012 (UTC) | Shame this only works in restaurants that price all their appetizers differently. [[User:Davidy22|Davidy22]] ([[User talk:Davidy22|talk]]) 03:18, 13 October 2012 (UTC) | ||
− | |||
− | |||
I have a hunch that the seven fruit cups are pretty intentional as the first item on the menu and the simplest solution possible. | I have a hunch that the seven fruit cups are pretty intentional as the first item on the menu and the simplest solution possible. | ||
I was about to write a script to solve the problem through random selections and was going to optimize for speed by limiting the maximum times an item could be order to floor(15.05/price). Thus, one could order up to 2 sample plates, 3 moz sticks, 5 of the hot wings/side salad/french fries or 7 fruit cups without going over budget. (side note: you can always with these prices squeeze in a fruit cup with the exception of the 7 fruit cups). I found the "trivial" solution on the first step of the "preliminary" work for that script and then took a catnap. | I was about to write a script to solve the problem through random selections and was going to optimize for speed by limiting the maximum times an item could be order to floor(15.05/price). Thus, one could order up to 2 sample plates, 3 moz sticks, 5 of the hot wings/side salad/french fries or 7 fruit cups without going over budget. (side note: you can always with these prices squeeze in a fruit cup with the exception of the 7 fruit cups). I found the "trivial" solution on the first step of the "preliminary" work for that script and then took a catnap. | ||
Line 9: | Line 6: | ||
Note to self: try this sometime in the real world using a real menu. [[User:Katya|Katya]] ([[User talk:Katya|talk]]) 02:17, 23 November 2012 (UTC) | Note to self: try this sometime in the real world using a real menu. [[User:Katya|Katya]] ([[User talk:Katya|talk]]) 02:17, 23 November 2012 (UTC) | ||
− | |||
Note: Traveling Salesman Problem ''might'' be mentioned ''also'' because both this problem and the Knapsack problem to be solved belong to set of '''[[wikipedia:NP-complete|NP-complete]] problems'''; a Knapsack problem can be transformed in polynomial time to Traveling Salesman Problem, and solution of Traveling Salesman Problem can be transformed in polynomial time to Knapsack problem solution. --[[User:JakubNarebski|JakubNarebski]] ([[User talk:JakubNarebski|talk]]) 16:00, 11 December 2012 (UTC) | Note: Traveling Salesman Problem ''might'' be mentioned ''also'' because both this problem and the Knapsack problem to be solved belong to set of '''[[wikipedia:NP-complete|NP-complete]] problems'''; a Knapsack problem can be transformed in polynomial time to Traveling Salesman Problem, and solution of Traveling Salesman Problem can be transformed in polynomial time to Knapsack problem solution. --[[User:JakubNarebski|JakubNarebski]] ([[User talk:JakubNarebski|talk]]) 16:00, 11 December 2012 (UTC) | ||
− | |||
− | + | ||
In [http://www.maa.org/mathhorizons/MH-Sep2012_XKCD.html an interview] with the Mathematical Association of America Randall said that the trivial answer to this problem was a mistake. [[User:Xrays Knock Charms Down|Xrays Knock Charms Down]] ([[User talk:Xrays Knock Charms Down|talk]]) 03:00, 6 May 2013 (UTC) | In [http://www.maa.org/mathhorizons/MH-Sep2012_XKCD.html an interview] with the Mathematical Association of America Randall said that the trivial answer to this problem was a mistake. [[User:Xrays Knock Charms Down|Xrays Knock Charms Down]] ([[User talk:Xrays Knock Charms Down|talk]]) 03:00, 6 May 2013 (UTC) | ||
:I added this very interesting info to the explanation - at first as a trivia, but then I realized that it would not be seen by everyone - as you often do not read below the transcript. Why would you, you do not need to see what was in the comic again... So I moved it up to the solution part, because to me it is a very important fact about this comic. An error by Randall... But Dgbrt keeps moving this info away from the solution. I have understood now that the trivia should be below the transcript - although I cannot see why this should be so - as I have just described. But who says that this info should be a trivia item? It was I who put it there (by mistake?) at first. I will try not to start an editing fight here, but still think there should at least be a mention in the explanation that it was a mistake - in case you do not realize there is a trivia section below. I have used this page a lot lately, and had not found out before, that it was always below. There is not that many pages with trivia sections [[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 11:02, 10 March 2014 (UTC) | :I added this very interesting info to the explanation - at first as a trivia, but then I realized that it would not be seen by everyone - as you often do not read below the transcript. Why would you, you do not need to see what was in the comic again... So I moved it up to the solution part, because to me it is a very important fact about this comic. An error by Randall... But Dgbrt keeps moving this info away from the solution. I have understood now that the trivia should be below the transcript - although I cannot see why this should be so - as I have just described. But who says that this info should be a trivia item? It was I who put it there (by mistake?) at first. I will try not to start an editing fight here, but still think there should at least be a mention in the explanation that it was a mistake - in case you do not realize there is a trivia section below. I have used this page a lot lately, and had not found out before, that it was always below. There is not that many pages with trivia sections [[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 11:02, 10 March 2014 (UTC) | ||
− | |||
− | |||
− | |||
− | + | ||
I was bored and tried to find a solution for fun. I found the more complex one quite fast by chance. It was actually the second combination I tried. I did not realize you could just add seven fruit cups because I was so set on starting with the sampler plate. Now I am not sure if I should be glad, because I was so lucky, or annoyed that my fight-the-boredom-idea did not work out, or even more annoyed that I never have that kind of luck in the lab where I could really use it for finding the one thing out of a thousand possible causes for "why-does-my-experiment-not-work" which actually will give me some usable data. | I was bored and tried to find a solution for fun. I found the more complex one quite fast by chance. It was actually the second combination I tried. I did not realize you could just add seven fruit cups because I was so set on starting with the sampler plate. Now I am not sure if I should be glad, because I was so lucky, or annoyed that my fight-the-boredom-idea did not work out, or even more annoyed that I never have that kind of luck in the lab where I could really use it for finding the one thing out of a thousand possible causes for "why-does-my-experiment-not-work" which actually will give me some usable data. | ||
[[Special:Contributions/84.56.77.11|84.56.77.11]] | [[Special:Contributions/84.56.77.11|84.56.77.11]] | ||
− | |||
This explanation is thorough, and I like being thorough, but it seems to be a bit of overkill. I copy-edited it a bit, but I have a couple qualms. This is not really the knapsack problem, as it does not attach values to the items (as mentioned). It is more of a {{w|subset sum}} problem, which admittedly could be considered a variant of the knapsack problem. Secondly, I don't see why we need to go into detail about the movie Office Space. --[[User:Quicksilver|Quicksilver]] ([[User talk:Quicksilver|talk]]) 18:34, 22 August 2013 (UTC) | This explanation is thorough, and I like being thorough, but it seems to be a bit of overkill. I copy-edited it a bit, but I have a couple qualms. This is not really the knapsack problem, as it does not attach values to the items (as mentioned). It is more of a {{w|subset sum}} problem, which admittedly could be considered a variant of the knapsack problem. Secondly, I don't see why we need to go into detail about the movie Office Space. --[[User:Quicksilver|Quicksilver]] ([[User talk:Quicksilver|talk]]) 18:34, 22 August 2013 (UTC) | ||
:I did some clean-ups, but the the "In computational complexity theory" still needs a review.--[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 20:19, 22 August 2013 (UTC) | :I did some clean-ups, but the the "In computational complexity theory" still needs a review.--[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 20:19, 22 August 2013 (UTC) | ||
− | |||
− | |||
Inspired by this comic, somebody has actually created an ordering site which tries to give you an order from a restaurant in your area (US only I think) totalling a specific amount [http://www.np-food.com NP Food]. Worth including above? -- [[User:Copito|Copito]] ([[User talk:Copito|talk]]) 20:43, 8 November 2013 (UTC) | Inspired by this comic, somebody has actually created an ordering site which tries to give you an order from a restaurant in your area (US only I think) totalling a specific amount [http://www.np-food.com NP Food]. Worth including above? -- [[User:Copito|Copito]] ([[User talk:Copito|talk]]) 20:43, 8 November 2013 (UTC) | ||
That site doesn't work for me. —[[User:TobyBartels|TobyBartels]] ([[User talk:TobyBartels|talk]]) 10:07, 19 November 2013 (UTC) | That site doesn't work for me. —[[User:TobyBartels|TobyBartels]] ([[User talk:TobyBartels|talk]]) 10:07, 19 November 2013 (UTC) | ||
− | |||
− | + | [[:user|Roman Czyborra]] did post this at the explain: | |
− | [[user | ||
;The Solution | ;The Solution | ||
… can be calculated as | … can be calculated as | ||
Line 47: | Line 34: | ||
== [[215,355,355,580],[215,215,215,215,215,215,215]] | == [[215,355,355,580],[215,215,215,215,215,215,215]] | ||
I don't think this is a helpful explain. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 19:11, 14 May 2014 (UTC) | I don't think this is a helpful explain. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 19:11, 14 May 2014 (UTC) | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |