アルゴリズム（複数ナップザック問題？）について

質問

現在以下のような問題を考えています。

例えば価値が[3, 4, 4, 5]の4つのもの全てを、複数のナップザックに入れるときに

ナップザックAに[3, 5]　= 8
ナップザックBに[4, 4] = 8
標準偏差　= 0

もしくは

ナップザックAに[3, 4, 4, 5] = 16
標準偏差　= 0

と入れた場合にナップザックの標準偏差（ばらつき）が最小になります。

ここで、ナップザックの数に何個以上、何個未満という制約を与えた際に、与えられたものを全てのナップザックに入れた際に、標準偏差が最も小さくなるアルゴリズム(excel, VBAなど）がありましたら紹介して頂けないでしょうか。

なお、ナップザックに入れるデータは100個程度を想定しています。
どうかよろしくお願い申し上げます。

回答No.1

いけだ ひろし（@ike-2000） · ベストアンサー

参考程度で読んでください。
このような問題は解いたことはないのですが、やはりΣ(Xi-x(平均値))**2が効いてくるのでナップザックに入れるXiをまとめることに注力すれば良いと考えます。

これの運用が気になります。
(1)オンラインでなければ(夜間バッチでよければ)、1つのナップザックに100程度でナップザックも100程度であればあまりアルゴリズムを気にせず全計算でよいのではないかと考えます。

(2)オンラインなのであれば1回とにかく適切な手順で「価値」を配置した後に標準偏差が最小のものと最大のものとでそのナップザックの中の適当な「価値」を入れ替える、または、移すなどしてより小さくしていくという方法です。これを再帰的(有限回)に繰り返せばある程度小さく出来ると思います。

(1)では最適な解が求まりますが(2)はおそらく漸近的です。ロジックはご勘弁願います。

お礼

回答どうもありがとうございます。
(2)のアイデアはなかなかいいですね！
最終的な目的として、時間をかけた最適解より、短時間で漸近的な解を求めたいので、(2)のアイデアを参考にアルゴリズムを作ってみたいと思います。