Packing a suitcase

Before we travel we always have the dilemma which items to take as there are always more than we have room for. This is frustrating, because it means that we need to make some tradeoffs again. Since we can't take everything that we want, moving can become uncomfortable.

The suitcase we use to pack the items has certain physical dimensions. For instance, if it is 67cm high, 45cm wide and 29cm deep, this means that its maximal theoretical volume would be 0.087435m3 assuming it has the form of a rectangular parallelepiped. Therefore, one of the restrictions that we have is regarding the volume of the objects we can put inside. Another restriction is their weight. Typically we cannot bring too much weight into the luggage compartment of a public vehicle, regardless of whether it is a bus or an airplane. We may be able to take only up to 20kg, where each additional kilogram either won't be allowed or would add an exorbitant cost.

How do we decide then which items to take and which to leave?

This is an instance of the knapsack problem. We could proceed by trying to fill our suitcase with the items that show the best estimated price/weight ratio, in reversed sorted order, until we either can't put another item or we have to choose one of smaller weight.

But such a definition doesn't consider the volume constraint. Some items are lightweight, but quite voluminous (e.g. toilet paper), so we may exhaust our available volume before we reach the maximal weight bound. Other items, like dumbbells, are smaller in volume, but quite heavy. This means that we need to have a balanced mix of items in our luggage.

Additionally, we may have trouble to determine the relative worth of the objects we want to carry. Some of them might have lost some of their value (hardware) or may have an added sentimental value (mementos). Some of them may be more beautiful than others.

Given all these factors that could influence our choice, we could divide them into two categories: 1) value adding and 2) constraint inducing. In each category we could multiply the numbers we can assign to each factor and divide the result for the first category by the result of the second, repeating for each item we could potentially pack. This will give us comparable numbers since we apply the same process to all items in the same way. Optionally, we could normalize the values by dividing by the maximal number in the column to work with values in the interval [0, 1]. The larger the final value, the more important this object is to be included in our luggage. This value can determine the packing order of the items, where the normalization step doesn't affect it.

Here is a sample data we would like to analyze this way:

ItemEstimated pricePerceived valueVolume (m3)Weight (kg)
Diaries11500.0081.5
Laptop9904000.0062.4
Clock10150.00050.15
USB stick30450.00010.02
Netmag issues150800.0142.6
Sunglasses20100.00070.12
Towel25200.0040.48
Sweater35250.0020.3
Socks560.00030.02
WiFi router170350.0020.55
T-shirts55100.0040.45
Can opener520.000250.1
City map15180.00040.24
Digital camera6202800.00030.3
Trousers45150.0070.8
Underwear20100.00060.35
Casualwear90200.0091.3
Blanket4050.0222.2
Sheets2060.00050.55
Graphic tablet320300.00070.4
External HDD200700.00020.45
Dictionary25100.00030.3
Cookbook2030.0010.5
Batteries100.50.000150.1
Shower gel530.00020.25
Shaving foam1060.00030.3
Conference ticket80350.00010.01
Desk lamp25150.0080.6
GSM adapter1550.00020.18
Pencils520.000150.05
Paper840.0010.85

Based on this table and the calculation mentioned above, we can compute the order in which we need to pack the items — Conference ticket, Digital camera, USB stick, External HDD, Graphic tablet, Laptop, WiFi router, Socks, City map, Dictionary, Sunglasses, GSM adapter, Clock, Sweater, Pencils, Underwear, Shaving foam, Sheets, Can opener, Batteries, Netmag issues, T-shirts, Shower gel, Towel, Casualwear, Trousers, Cookbook, Desk lamp, Paper, Diaries, Blanket. The total weight is 18.42kg (within bounds), while the volume is 0.09385m3 (outside the bounds mentioned above). This means that we'll have to take out some items. If we remove the last item on the list, the volume becomes 0.07195m3, which is now within bounds as well. We can only hope that the place we'll go to will have a blanket.