Bin packing bruteforce method

问题:

I need to make program that solves bin packing problem, but I already made first fit and greedy algorithms, but my lecturer says in some cases it won't find the minimal solution to the problem. So i decided to try bruteforce, but I have no clue how it should check all possible solutions. So yea.. can someone explain to me or give pseudo-code or something. I would appreciate a lot.

回答1:

Note that bin-packing is an NP-hard problem, basically meaning it will take excessively long to run brute force on it, even for relatively small input, so brute force for NP-hard problems is almost never a good idea. The link above shows some alternatives (or approximations). But I'll continue...

Recursion makes brute force easy. Once you understand a basic recursive algorithm, continue reading...

Basic idea: (for 3 items, 2 bins, assuming everything fits, if it doesn't just skip that branch)

Put the first item in the first bin.
  Put the second item in the first bin.
    Put the third item in the first bin.
      Woo-hoo! We have a solution!
    Remove the third item from the first bin and put it into the second bin.
      Woo-hoo! We have a solution!
    Remove the third item from the second bin.
  Remove the second item from the first bin and put it into the second bin.
    Put the third item in the first bin.
      Woo-hoo! We have a solution!
    Remove the third item from the first bin and put it into the second bin.
      Woo-hoo! We have a solution!
    Remove the third item from the second bin.
  Remove the second item from the second bin.
Remove the first item from the first bin and put it into the second bin.
  Put the second item in the first bin.
    Put the third item in the first bin.
      Woo-hoo! We have a solution!
    Remove the third item from the first bin and put it into the second bin.
      Woo-hoo! We have a solution!
    Remove the third item from the second bin.
  Remove the second item from the first bin and put it into the second bin.
    Put the third item in the first bin.
      Woo-hoo! We have a solution!
    Remove the third item from the first bin and put it into the second bin.
      Woo-hoo! We have a solution!
    Remove the third item from the second bin.
  Remove the second item from the second bin.
Remove the first item from the second bin.

(See how many steps there is already? And this is just for 3 items and 2 bins)

Pseudo-code:

recurse(int itemID)
  if pastLastItem(itemID)
    if betterThanBestSolution
      bestSolution = currentAssignment
    return
  for each bin i:
    putIntoBin(itemID, i)
    recurse(itemID+1)
    removeFromBin(itemID, i)

回答2:

Brute force just tries every combination.

To write the code for brute force, consider this trick: Suppose we want to visit all combitions of 8 queens, without hardcoding 8 nested loops. Just think of the following octal number consisting out of 8 zero's.

00000000

Then write a single loop that increases it in an octal numeric system:

00000001
00000002
00000003
...
00000007 // 7 + 1 = 10
00000010
00000011
00000012
...
77777776
77777777

That tries all combinations, without having to hard code 8 inner loops. Replace 8 by n and the same code still works.

回答3:

You can obviously do better than just brute force. First you calculate the minimum number of bins. If you have bins of size 100, and items with a total size of 1,234 then they are not going to fit into 12 bins but might fit into 13.

With 13 bins, you would have unused space of 66 (1,300 - 1,234). Since 5 x 13 = 65, there must be at least one bin with a size of 6 unused. So if you have any items of size 6 or less, you can leave it out of the calculation because you can fit it anyway in the end (of course you need to check with the actual numbers you have, but anyway, small items can be removed from the search).

If two items fill a bin exactly, then you don't need to consider any solution where they don't fit together.

From then on you use dynamic programming, except that you always use the largest unused item as the first item in a fresh bin, you always fill a bin with items in descending order, you always add more items until nothing fits, you never consider combinations where all items are smaller or the same size as in another combination. And finally, when you found a combination that is as good as the minimum number of bins that were required, you found an optimal solution.