xkcd and sending it in.

I bet I wasn't even the first.

But it is neat that that's the first time I ever wrote a python script.

Staying up an extra hour to code up a simple (i.e. not useful for totals > $1k) solution to I bet I wasn't even the first.

But it is neat that that's the first time I ever wrote a python script.

## Comments

kvarko'Some writers feel that knapsack cryptosystem is a misnomer because the cryptosystem is actually based on the subset sum problem. For example, Douglas R. Stinson points out that a knapsack problem usually refers to one “involving selecting objects with given weights and profits in such a way that a specified capacity is not exceeded and a specified target profit is attained.” [96, p. 190]. That is, a knapsack problem, as he sees it, is to maximize Spi*xi subject to Swi*xi £ c, where pi and wi are the profit and the weight of object i respectively, xi is a binary variable signifying whether object i is selected or not, and c is the capacity. And the subset sum problem usually is defined as one under which a finite set of natural numbers is given and we are asked whether there is a subset of this set whose elements sum up to a certain target, which is also a natural number. On the other hand, there are people (see [2], [32], and [39] for example) who define a knapsack problem (or a form thereof) exactly as the subset sum problem described above. And it is exactly [32] and [39] that Merkle and Hellman cited in their paper as the description of the knapsack problem on which they based their cryptosystem.'

So it would seem that xkcd has the same definition -- unless he wants to give a better weight to a mixed order of appetizers than to 7 orders of mixed fruit :)