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
items:

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s