Talk:287: NP-Complete

Shame this only works in restaurants that price all their appetizers differently. 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 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. Of course, since the nontrivial solution involves the same item as the trivial solution, one could just pick a number, multiply by that number, subtract one unit, and pick two other items, whose prices were not set yet, and adjust their prices to add up accordingly just to ensure both trivial and nontrivial solutions lest anyone actually write a program to solve the problem through brute force as oppose to through wit. Why seed? Because to not have a nontrivial solution would be so much like Blackhat. Note to self: try this sometime in the real world using a real menu. 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 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. --JakubNarebski (talk) 16:00, 11 December 2012 (UTC)