The Knapsack Problem and its possible applications on Amazon.com

I’ve never been much of an online shopper. I avoided shopping online as much as I could. Until recently.

I discovered Amazon’s Mechanical Turk just before I left India. I created an ID with my India address and forgot all about it.

Until a few weeks back. I made some money on MTurk by participating in surveys, transcription, stuff like that. And then I wanted to transfer it to my US account.

Nope, nada. You can’t. You can only get it delivered to your India address. Which will take six weeks. And $4. And you can’t change the address unless you delete your account (and lose your money) and create a new one.

So the only other option I have is to convert it to Amazon.com balance. Which I did.

And after buying stuff for friends and family on the website, I now have a modest amount left to spend on myself. Let’s say I have $15.

I want to know what I can get for $15 in books. What sort of combinations. Woody Allen + Milan Kundera? Artemis Fowl + Le Petit Nicolas? What am I missing out on? What can I buy which is better?

So… this can be considered a knapsack problem. It occurred to me after my situation reminded me of this xkcd cartoon:

So what is the Knapsack problem? I’ll explain the simpler, more common 0/1 Knapsack Problem. So you have a set of items. Each item has a weight w and a value v. The knapsack can hold at most a weight of W. The problem is to choose which items to fill in the knapsack, such as to maximize the total V in the knapsack, while keeping the total weight under W. You can learn more here.

My Amazon.com problem can be considered a knapsack problem with the weight w of each item as its price, and the value v as how much Amazon thinks I’ll like the item. That of course is possible using collaborative filtering (yes! I know a term!) and other techniques. They can also use their ‘frequently bought together’ feature here.

Would others find it useful? Yes, if they are on a fixed budget like I am. Or if they want to buy just enough to be eligible for Free Super Saver Shipping.

Would it be possible in real time? I’m sure something can be worked out there.

And…. crowdsourcing this… any recommendations for nice books worth buying under $15?

On an aside, it’d be nice if WordPress.com had suggestions for most-frequent tags, and asked if we want these tags to be converted into categories.

And… Happy Thanksgiving! Wish you the best of Black Friday deals!