Bin包装强力方法 [英] Bin packing bruteforce method

问题描述

我需要制作解决bin打包问题的程序，但我已经制作了第一个适合和贪婪的算法，但我的讲师说在某些情况下它不会找到问题的最小解决方案。所以我决定尝试使用暴力，但我不知道它应该如何检查所有可能的解决方案。所以是..有人可以向我解释或给出伪代码或其他东西。我会很感激。

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.

推荐答案

请注意 bin-packing 是一个NP难题，基本上意味着它需要花费过长的时间才能对它施加蛮力，即使对于相对较小的输入，所以对于NP难问题的蛮力几乎是永远不是一个好主意。上面的链接显示了一些替代方案（或近似值）。但我会继续......

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...

基本思路:(对于3个项目，2个箱子，假设一切都合适，如果它不只是跳过那个分支）

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.

（看看已经有多少步骤？这只适用于3个项目和2个箱子）

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

伪代码：

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

这篇关于Bin包装强力方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！