C#でビンパッキング問題を解く(2)


[前回](https://qiita.com/gushwell/items/65d348fa3a6261e65630)は、Wikipediaの「[ビンパッキング問題](https://ja.wikipedia.org/wiki/ビンパッキング問題)」に載っている２つのアルゴリズムをそっくりそのままC#で実装してみました。

この２つのアルゴリズムは、荷物の全体像が分からないという前提のアルゴリズムです。もし全体像が把握できるのならもっと賢い結果を出すことができるかもしれません。

ということで、考えてみました。

## アルゴリズムAの改良版アルゴリズム

アルゴリズムAは、最も空きが多いビンに荷物を入れてゆく解法です。これをすこし改良してみます。

1. 荷物の総量を求め、最低限必要なビンを用意する。
2. 荷物を軽い順に並び変える
3. 荷物を空いている容量が最大のビンに詰める。
4. どのビンにも荷物が入らないとき、新しいビンに詰める。

と、こんな感じです。

実際に物理的に荷物を並び変えるのは現実的ではありませんが、コンピュータで結果を求め、その結果に従って、荷物を積んでいくようにすれば、現実問題にも適用できるはずです。

結果によっては、一番最初の荷物を、一番最後のビンに入れないといけないといったことが起こりえます。実際に荷物を詰めるときには、荷物を一時的に別の場所に置いておかなくてはなりません。これは困った状況です。しかし、その場合であっても実際には最後のビンに入れる必要はなく、今空いている空のビンに入れればよい(これが最後のビンと認識させる)ので、対応はできそうです。

問題は、ビンを置く場所が足りないというケースですね。そういったケースに対応するには、「いちどに置けるビンの数」という新たな制約を付けたアルゴリズムを考える必要がありますが、今回はそこまではやっていません。


## 改良したコード

クラス名をBinPackingSolver11としました。安易なネーミングですみませんm(_ _)m

前回のコードと異なるのは、Solveの前半部分と、foreachの要素取得のところで並び替えをしているところです。foreachの中はまったく同じコードになっています。

IBinPackingインターフェースについては、[前回](https://qiita.com/gushwell/items/65d348fa3a6261e65630)のコードを見てください。

```csharp
class BinPackingSolver11 : IBinPacking {

    public int BinSize { get; set; }

    public BinPackingSolver11(int size) {
        this.BinSize = size;
    }

    public ICollection<ICollection<int>> Solve(int[] items) {
        // 最低限必要なビンを用意し、listに入れる
        int total = items.Sum();
        int bincount = total / BinSize + ((total % BinSize == 0) ? 0 : 1);
        var binList = new List<ICollection<int>>();
        for (int i = 0; i < bincount; i++) {
            List<int> bin = new List<int>();
            binList.Add(bin);
        }

        // 各項目をビンに入れてゆく
        foreach (var n in items.OrderByDescending(a => a)) {
            // 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;
    }
}
```

## 確かめてみる

それでは、本当に改良されたのかどうかを確かめてみます。

BinPackingSolver1, BinPackingSolver11 の２つのクラスに同じデータを食わせて比較するコードを書いてみました。

```csharp
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinPackingApp {
    class Program {
        static void Main(string[] args) {
            while (true) {
                (var items, var binsize) = InputDate();
                if (items == null)
                    break;
                {
                    var bp = new BinPackingSolver1(binsize);
                    var r = bp.Solve(items);
                    PrintResult(r);
                }
                {
                    var bp = new BinPackingSolver11(binsize);
                    var r = bp.Solve(items);
                    PrintResult(r);
                }
            }
            Console.ReadLine();
        }

        private static (int[], int) InputDate() {
            Console.Write("荷物の重さ(カンマ区切り)=> ");
            var itemsText = Console.ReadLine();
            if (string.IsNullOrWhiteSpace(itemsText))
                return (null, 0);
            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());
        }
    }
}
```

## 実行してみる

それでは、実行してみます。
結果を表示している１つめのブロックが改良前、２つめのブロックが改良後です。
確かに、改良後のほうが良い結果を出しています。

```
荷物の重さ(カンマ区切り)=> 33,61,58,41,50,21,60,64
1台のコンテナの容量=> 120
   94: [33,61]
   99: [58,41]
   71: [50,21]
   60: [60]
   64: [64]

   85: [64,21]
   94: [61,33]
  101: [60,41]
  108: [58,50]

荷物の重さ(カンマ区切り)=> 33,61,58,41,50,21,60,64,34,54,65
1台のコンテナの容量=> 120
   94: [33,61]
   99: [58,41]
   71: [50,21]
   94: [60,34]
  118: [64,54]
   65: [65]

  119: [65,33,21]
   98: [64,34]
  102: [61,41]
  110: [60,50]
  112: [58,54]

荷物の重さ(カンマ区切り)=> 33,61,58,41,50,21,60,64,23,45,67,78,89
1台のコンテナの容量=> 120
   94: [33,61]
   99: [58,41]
   71: [50,21]
   83: [60,23]
  109: [64,45]
   67: [67]
   78: [78]
   89: [89]

  112: [89,23]
  111: [78,33]
  108: [67,41]
  109: [64,45]
  111: [61,50]
  118: [60,58]
   21: [21]
```


次回は、アルゴリズムBを改良してみたいと思います。


[続く...](https://qiita.com/gushwell/items/d09bda6cc2c408f4128d)

---

この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。