Problem 3: Gotta Max Profits

I’m a determined and ferocious trader on wall street. I only care about maximizing profits. An adaptive manipulator, I’m always the first person to react to (or rather to help my company adapt to) changes in the rules of the wall street money game. Yesterday, some rules pertaining to profits displays (on the floor of the main market) got changed.

Hitherto, maximum profits made by my company were displayed on the floor in a simple and intuitive way. So the only thing we needed to do to keep track of our max profits was to pipe the displayed maximum profits to our wall street data repository. But starting today, no maximum profits will be displayed. Only “crude” stock changes will be displayed. For example, the stock changes for the day (collected each hour) might look like this: [-2, 11, -4, 13, -5, 2].

Now I have to make some algorithm to compute the maximum profits I made during the day. For example, the maximum profit (from the data set above) is 20 over the subarray [11,-4,13].

Can you help construct an algorithm to solve this problem? I’m actually a good trader I promise.

Solution to Problem 2: Stripping Down My Luggage

The interesting thing about this problem is that there are so many ways to solve this problem. I’d recommend solving this problem by hand, no matter the algorithm you intend to use. You shouldn’t have to solve this problem via code.

Some methods you could use to solve this problem:

  • Easy brute force
  • dynamic programming (notice this problem is reducible to the Knapsack problem)
  • inspection

Anyways, my solution to the problem that fits all selected items in the 3kg remaining space and maximizes the total Preference index is to select the following

Item Weight Preference
WW2 Galilean binoculars 0.5kg 5
Bufferfly knife 0.5kg 2
Camera 0.5kg 4
Laptop 1.5kg 6

Sum of selected item weights = 3.0kg
Sum of item preferences = 17

This problem is really easy but the point was to introduce you to the Knapsack problem.

Problem 2: Stripping Down My Luggage

I’d be leaving Budapest after Christmas. I hear Budapest is even more beautiful during the Christmas season. That’s plausible. So I’d stay in Budapest until the last day of this year. Today I spent some time thinking about how much stuff I can take out of Budapest. Apparently, Lufthansa allows me to check in only one bag and carry on one bag. Ridiculous, right?

But anyways I need to figure what I can put into the bag to check in and what I’ll have to mail somehow to the States. I have a list of things I’ve bought so far and things I wish to buy + how much these things weigh. The tricky thing is that there’s no clear positive or negative correlation between things that I want (or prefer) to take and the weight of these things. For example, I have a cup that I like that weighs 1kg, a 0.8kg World War 2 Galilean binoculars I bought today that’s kind of expensive and that I really like, and another WW 2 artifact, a butterfly knife that weighs 0.5kg. I don’t really like the butterfly knife but I think it’s better if I put it in the checked bag rather than mail it. I feel U.S customs might delay its entry if I mail it.

So my dilemma is to try to fit all the articles I’ve bought, the ones that I plan to buy, and the ones that I already have into a 23kg bag. Let’s assume that the
weight of all the items I came with (altogether) is about 20kg. The remaining space available is obviously 3kg. Here’s a list of the potential articles:

Item Weight Preference
Mashery Cup 1kg 4
WW2 Galilean binoculars 0.5kg 5
Bufferfly knife 0.5kg 2
Camera 0.5kg 4
Laptop 1.5kg 6
Soccer boots 1.5kg 3
Textbooks 2.0kg 3

To make it easier for me to know which items I should take and which I shouldn’t,
I associated each item with a preference number. The more I like an item, the higher
it’s preference number.

Another way of stating this problem is: I have a max space (3kg). I need to
fill that space with items from the above list. But in selecting the items, I wish
to maximize the total Preference of the selected items.

This problem is pretty easy to solve and there are many known heuristics and
algorithms you can use to solve this problem. Check out the solution here.