Packing Problem
- From: David C. Ullrich <dullrich@xxxxxxxxxxx>
- Date: Mon, 19 May 2008 15:36:09 -0500
Say we have a bunch of objects of varying sizes
that we want to pack into a bunch of fixed-size
bins - the problem is to find the packing that
minimizes the number of bins. (To clarify
various possible ambiguities, say they're files
in a directory on a computer that we want to
backup onto a bunch of CD's.)
My impression is that no efficient algorithm
for an optimal solution is known(?). My much
weaker impression is that this problem is known
to be in class [whatever], so that an optimal
solution would be equivalent to an optimal solution
to many other problems(?).
But this is not homework - I actually _do_ have
a bunch of files that I want to back up onto a
pile of CDs. Does the obvious algorithm give
a solution that's close to optimal? (I haven't
tried to look up the answer, thinking that
someone who knows would enjoy explaining; also
if I just looked up the answer then it wouldn't
appear here on sci.math).
Also are there any reasonably simple improvements
to the obvious algorithm that give results enough
better to be worthwhile?
What I mean by the obvious algorithm: Sort
the files in order of decreasing size F_1, F_2,...
Number the CDs, C_1, C_2, ... . Put F_1 on C_1.
For each n in turn, put F_n on C_m, where m is
the smallest number such that C_m still has
room for F_n.
David C. Ullrich
.
- Follow-Ups:
- Re: Packing Problem
- From: Ray Vickson
- Re: Packing Problem
- From: Ray Vickson
- Re: Packing Problem
- Prev by Date: Re: volume of a cone
- Next by Date: Re: The quaternion group as a product
- Previous by thread: Difficult integral
- Next by thread: Re: Packing Problem
- Index(es):
Relevant Pages
|
