April 23, 2009

solving UHAUL

a few of my friends have moved in the past few weeks, and this has sparked an interesting discussion in my head. like any other task, my mind constantly searches for the optimal solution. because of this, i thoroughly enjoy cramming boxes of different shapes and sizes into a UHaul truck, attempting to fit as much as possible in one go. sound like a familiar problem?

enter KNAPSACK. a common cs problem that seems very similar. a brief translation to this problem would be: given my possessions (the items,) and the UHaul truck (my knapsack,) maximize the amount of stuff i can cram into the truck.

however this variation has a few curveballs:
  • in KNAPSACK, items are usually just real numbers, here they are objects with a volume.
  • this means that you could have a subset whose overall size is the largest w/o surpassing the volume of the truck, but you are now confronted with the task of actually finding an orientation of the items in container that actually fits everything.
  • not only do you have volume, but i think shape might be a pretty weird variable in the item set.
  • you realistically want to value/prioritize which items you must include like your bed or dresser or tv.
  • at a certain point, if not all possessions can be fit in the container at the same time, the problem shifts from maximizing usage to minimizing the number of containers needed to consume all items.
  • you normally are doing things in a pipeline manner, (sorting, packing into boxes, moving boxes into truck.) so you might not have the omniscient view of all items as you start to pack the truck, and ymmv based on when you see certain items. this throws the traditional dynamic programming approach out the window.
so we can try to simplify this problem a little bit before trying to solve it:
  • confine all items to be rectangular prisms
  • maybe even start with 2D (packing rectangles,) which i want to dub PLANTING for maximizing crop sections in the fields.
have you noticed i really enjoy citing cs problems in ALL CAPS?

No comments:

Post a Comment