容量の異なるビンと、指定されたサイズのオブジェクトがあります。目標は、これらのオブジェクトをビンに詰めることです。これまでは、ビンパッキング問題に似ています。しかし、ねじれは、各オブジェクトが別のオブジェクトと部分的にオーバーラップしていることです。したがって、オブジェクト1と2のサイズはs1とs2ですが、同じビンに入れると、埋められたスペースはs1+s2未満になります。オブジェクトの各ペアについてこの重複する値を知っていると仮定すると、この問題の元のビンパッキングのような近似アルゴリズムもありますか？
質問する
909 次
2 に答える
2
答えは、オブジェクトが壊れている可能性があると仮定して、オブジェクトの類似性をキャプチャする一種のツリーを使用することです。次に、欲張りアルゴリズムを実行して、ツリーに従ってビンを埋めます。このアルゴリズムには、3倍の近似限界があります。ただし、より良い答えもあるはずです。
私はこのスレッドからこの答えを得ましたが、答えを与えることによってこの質問を閉じたかっただけです。
于 2012-08-07T22:50:36.583 に答える
0
私がうまくいくと思う唯一のアルゴリズムは、ビンに収まらないアイテムを整理し、別のビンを使用することです。私は最初の適合アルゴリズムを意味するのではなく、一定期間待ってからアイテムに新しいビンを使用することを意味します。実際には、別のビンを使用できますか？これは実用的なアプローチです。つまり、次の例のように、ビンを左または右に拡大できます：http: //codeincomplete.com/posts/2011/5/7/bin_packing/。
于 2012-07-25T12:04:18.827 に答える