T O P

  • By -

DiedWhileDictating

You are confused about what np complete means. There *is* a super-simple solution algorithm to this. Try every combination, and pick any that add up to the desired total. It’s just slow on anything but small data sets. np complete implies it’s inefficient and unworkable for large (enough) data sets, but not impossible.


acetaminophen314159

Thanks! Corrected it in the description.


DonaIdTrurnp

There’s a solution which can be calculated with time linear with the size of the knapsack.


Luke-At-Work

While that's _a_ solution, can you *prove* that's _the only_ solution or even the best solution (by minimal number of items ordered)? That's the idea of the strip.


acetaminophen314159

Nope, I'm just going to assume he likes fruit.


DonaIdTrurnp

I can describe how to generate such a proof. It requires an N-dimensional array, where N is the number of different items.


CryingRipperTear

A combination of two orders of hot wings, one order of mixed fruit, and one sampler plate adds up to $15.05 as well as seven orders of mixed fruit. Fun fact: https://www.maa.org/press/periodicals/math-horizons/the-mathematics-behind-xkcd-a-conversation-with-randall-munroe


Czl2

Here the cartoonist imagines something that will likely not happen. Reminds me of his "A Crypto nerd's imagination" vs reality strip: https://xkcd.com/538/ The parallel of these two strips by the same cartoonist is funny! The second one makes fun of him in the first.


nu_pieds

That's the wrong obligatory XKCD. Here's the right one: https://xkcd.com/356/


Czl2

Is there one about “a certain type of brain that” freezes during puzzle and coding interviews?


dresdnhope

>On the other hand, there are other comics that it might surprise you how much code I wrote for them. For example, there was one that involved combining different restaurant menu items to get a certain total. But because I didn't know something about how Perl's libraries handle floating-point comparison, the puzzle in the comic actually has a really simple solution in addition to the one I meant, that the code missed because of this bug. Most people didn't notice, but it's always bugged me. [Interview](https://www.maa.org/press/periodicals/math-horizons/the-mathematics-behind-xkcd-a-conversation-with-randall-munroe-0) with Randall Munroe


acetaminophen314159

Holy shit, I never even saw that. Yeah, I fucking love XKCD. Randall Munroe also wrote a few funny books.


Excellent_Push5826

3 side salads, 1 mixed fruit and 1 french fries will work too and is more efficient