Reputation: 6940

Packing by weight

If I have a number of items less than one pound, and I want to efficiently pack them into one pound containers, should I do that by brute force? (Figure out all the various combinations, pack, and see which combination leads to the smallest number of packages?)

Is there a name for this sort of algorithm?

In my case, I don't have a large number of packages.

Upvotes: 2

Answers (5)

Arend

Reputation: 3761

You can look into the Algorithm Design Manual for descriptions of your problem:

Bin Packing http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

Knapsack problem http://www.cs.sunysb.edu/~algorith/files/knapsack.shtml

You can probably make it easier on yourself if you can define a fitting solution (good enough), rather then if you want to know the best solution.

Upvotes: 1

Joe Van Dyk

Reputation: 6940

I wrote the following Ruby program to solve this problem, it seems to work well.

https://gist.github.com/1398026

Upvotes: 0

malejpavouk

Reputation: 4445

It's NP complete problem. You dont have much better options, best would probably be some dynamic programming algorithm with pseudopolynomial (exponential) complexity.

Upvotes: 0

Cybercartel

Reputation: 12592

You can also look for 1d bin-packing or 2d bin-packing algorithm. If you don't have too much bins I suggest a brute-force algorithm but it seems to be a very hard problem.

Upvotes: 1

alvin

Reputation: 1196

you might want to look at the knapsack problem

Upvotes: 1

Packing by weight

Answers (5)

Related Questions