ビンパッキング問題とは
ビンパッキング問題は、与えられた荷物をできるだけ少ない箱（ビンやコンテナ）に詰める問題です。
例えば、荷物を詰めるコンテナがあり、そのコンテナには一定の重さまでしか荷物を詰め込めないとします。
この時、重さの異なる複数の荷物をどうやってコンテナに詰めれば、コンテナの数を少なくできるかを求めるのが、ビンパッキング問題です。
Wikipedia「ビンパッキング問題」を参照してください。
作成するプログラムの実行例
以下のようなプログラムを作成してみたいと思います。
項目に荷物の重さ（カンマ区切りで複数指定）を入力し、容量にビンに詰め込める最大の重さを入力すると、どのように詰め込んだら良いかを表示させるというものです。
荷物の重さ(カンマ区切り)=> 8,5,10,6,4,5,8,5,9,6,9
容量=> 30
29: [8,5,10,6]
22: [4,5,8,5]
24: [9,6,9]
表示される結果ですが、１行が一つのビンを表しています。[ ] に表示されるのがビンに入る荷物の重さ、: の左側はその合計の重さとなります。
この問題を解く万能なアルゴリズムはないということらしいです。まずは、Wikipedia「ビンパッキング問題」に載っている２つのアルゴリズムを実装してみます。
なお、この２つのアルゴリズムは、荷物の全体像が分からないという前提のアルゴリズムです。一つずつ荷物を渡され、どのビンに詰めていったらよいかを判断しながら、荷物を詰めていくというアルゴリズムになっています。
これを頭に入れて読んでいただければと思います。
アルゴリズムA (最も空きが多いビンに荷物を入れてゆく解法)
一つ目は、最も空きが多いビンに荷物を入れてゆく解法です。以下に示す方法で荷物を詰めていきます。
- 荷物を空いている容量が最大のビンに詰める。
- どのビンにも荷物が入らないとき、新しいビンに詰める。
アルゴリズムAのソースコード
アルゴリズムAのソースコードです。もう一つのアルゴリズムも実装する予定なので、インターフェース IBinPackingを定義しました。
アルゴリズムAを実現するクラスは、このこのインターフェースを実装します。
interface IBinPacking {
int BinSize { get; set; }
ICollection<ICollection<int>> Solve(int[] items);
}
// 解法A：最も空きが多いビンに入れていく解法
class BinPackingSolver1 : IBinPacking {
public int BinSize { get; set; }
public BinPackingSolver1(int size) {
this.BinSize = size;
}
public ICollection<ICollection<int>> Solve(int[] items) {
// 最初に一つのビンを用意する
var binList = new List<ICollection<int>>();
binList.Add(new List<int>());
// 各項目をビンに入れてゆく
foreach (var n in items) {
// nが入るビンを見つける （空きが最大のビン）
var target = binList.Select(b => new { Bin = b, Space = BinSize - b.Sum(t => t) })
.Where(x => x.Space >= n)
.OrderByDescending(x => x.Space)
.Select(x => x.Bin);
var bin = target.FirstOrDefault();
if (bin != null) {
// nが入るビンが見つかったので、そこに入れる
bin.Add(n);
} else {
// 見つからなかったので、新しいビンを用意する
List<int> bin2 = new List<int>() { n };
binList.Add(bin2);
}
}
return binList;
}
}
アルゴリズムAを利用するメインプログラム
それでは、このクラスを使って、問題を解くプログラムを書いてみます。
class Program {
static void Main(string[] args) {
(var items, var binsize) = InputDate();
var bp = new BinPackingSolver1(binsize);
var r = bp.Solve(items);
PrintResult(r);
Console.ReadLine();
}
// データの入力
private static (int[] ,int) InputDate() {
Console.Write("荷物の重さ(カンマ区切り)=> ");
var itemsText = Console.ReadLine();
var items = itemsText.Split(',')
.Select(x => int.Parse(x.Trim()))
.ToArray();
Console.Write("1台のコンテナの容量=> ");
var sizeText = Console.ReadLine();
int binsize = int.Parse(sizeText);
return (items, binsize);
}
// 結果を表示
private static void PrintResult(IEnumerable<IEnumerable<int>> result) {
var sb = new StringBuilder();
foreach (var bin in result) {
var list = string.Join(",", bin.Select(n => n.ToString()).ToArray());
var sum = bin.Sum();
sb.AppendLine($"{sum,5}: [{list}]");
}
Console.WriteLine(sb.ToString());
}
}
C#の新しい機能であるタプルを使ってみました。
なんか、思いのほか長いコードになってしまいましたが、それほど複雑なことはしていないので、順に読んでいけば理解できると思います。
それと面倒なので、入力値の検証はやっていません。
実行してみる
では、実行してみます。
荷物の重さ(カンマ区切り)=> 33, 61, 58, 41, 50, 21, 60, 64
容量=> 120
94: [33,61]
99: [58,41]
71: [50,21]
60: [60]
64: [64]
wikipediaの例に載っている値をそのまま使ってみました。
同じ結果がでましたが、最後の２つは、ずいぶんと空きがあるので、あまり良い結果とは言えませんね。
アルゴリズムB (最も空きが少ないビンに入れてゆく解法)
では、２つめのアルゴリズムで解いてみます。
- 荷物を空いている容量が最小のビンに詰める。
- どのビンにも荷物が入らないとき、新しいビンに詰める。
アルゴリズムAとの違いは、「最大」が「最小」になっただけですね。
これでどんな違いがでるのか興味深いですね。
ソースコード
アルゴリズムBは、BinPackingSolver2という名前でSolverクラスを作成しました。
// 解法０２：最も空きが少ないビンに入れていく解法
class BinPackingSolver2 : IBinPacking {
public int BinSize { get; set; }
public BinPackingSolver2(int size) {
BinSize = size;
}
public ICollection<ICollection<int>> Solve(int[] items) {
// 最初に一つのビンを用意する
var binList = new List<ICollection<int>>();
binList.Add(new List<int>());
// 各項目をビンに入れてゆく
foreach (var n in items) {
// nが入るビンを見つける （空きが最小のビン）
var target = binList.Select(b => new { Bin = b, Space = BinSize - b.Sum(t => t) })
.Where(x => x.Space >= n)
.OrderBy(x => x.Space)
.Select(x => x.Bin);
var bin = target.FirstOrDefault();
if (bin != null) {
// nが入るビンが見つかったので、そこに入れる
bin.Add(n);
} else {
// 見つからなかったので、新しいビンを用意する
List<int> bin2 = new List<int>() { n };
binList.Add(bin2);
}
}
return binList;
}
}
２つのコード(BinPackingSolver1,BinPackingSolver2)を比べてみると、ほとんど同じです。
OrderByDescendingしているか、OrderByしているかだけの違いです。
言葉で表した時も「最大」が「最小」になっただけでしたから、当たり前といえば当たり前ですね。
実行してみる
それでは、ProgramクラスのExecuteメソッドで、BinPackingSolver1をnewしているところをBinPackingSolver2に書き換えて実行してみます。
荷物の重さ(カンマ区切り)=> 33, 61, 58, 41, 50, 21, 60, 64
容量=> 120
94: [33,61]
120: [58,41,21]
110: [50,60]
64: [64]
これも、Wikipediaの記事と同じ結果となりました。
もし全体像が把握できるのなら
今回の例だと、アルゴリズムBがより良い解答を導き出しましたが、これはたまたまであって、いつもアルゴリズムBが良い解答を出してくれるとは限りません。実際にいくつかの例でやってみれば、わかると思います。
もっと賢いアルゴリズムはないものでしょうか？ 最初に触れたように、この２つのアルゴリズムは、荷物の全体像が分からないという前提のアルゴリズムです。もし全体像が把握できるのなら、もっと賢いやり方がありそうです。
ということで、別のアルゴリズムも考えてみたいと思います。
続く...
この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。