2

length定義されたand horizontal position(両方とも定数)を持ついくつかのアイテムがあるとしましょう:

1 : A      
2 :     B
3 :  CC
4 :  DDD   (item 4 start at position 1, length = 3)
5 :    EE  
6 : F

それらを垂直にパックしたいので、高さができるだけ小さい長方形になります。

これまで、アイテムをループし、その行に配置できるかどうかを行ごとにチェックする（つまり、他の何かと衝突しないことを意味する）いくつかの非常に単純なアルゴリズムがあります。場合によっては（偶然に）完全に機能することもありますが、最適でないソリューションになることもあります。

上記の例で得られるものは次のとおりです（ステップバイステップ）：

 A      |  A   B  |  ACC B  |  ACC B  |  ACC B  |  ACC B  | 
                                DDD   |   DDD   |  FDDD   |
                                            EE  |     EE  |

最適な解決策は次のとおりですが、

ADDDB 
FCCEE

length注：アルゴリズムを適用する前に、最初にアイテムを（降順で）並べ替えると、より良い結果が得られることがわかりました（ただし、それでも完全ではありません）。

合理的な時間内に最適なソリューションを提供するアルゴリズムはありますか? （すべての可能性を試すことは現実的ではありません）

編集:これは、並べ替えのトリックを使用しても機能せず、TylerOhlsenが提案したものを使用しても機能しない例です(彼の答えを理解していない場合を除く):

1 : AA
2 :    BBB
3 :   CCC 
4 :  DD

与えるだろう：

AA BBB
  CCC 
 DD

最適解 :

 DDBBB
AACCC
4

2 に答える 2

-2

これは古典的なナップザック問題です。@amit が言ったように、それは NP-Complete です。最も効率的なソリューションは、動的計画法を使用して解決します。

ウィキペディアのページは非常に良いスタートです。この問題を解決するアルゴリズムを実装したことはありませんが、NP-Complete でもあるマインスイーパ ゲームとの関係を調べました。

ウィキペディア: ナップザック問題

于 2013-01-09T13:57:45.013 に答える