ビンパッキング

先生のところのをC#2.0に移植してみた。
http://blog.livedoor.jp/logopt/archives/2005-07.html#20050703

using System;
using System.Collections.Generic;

/// <summary>ビンパッキング</summary>
class BinSet
{
    private decimal capacity;
    /// <summary>1本のビンの容量</summary>
    public decimal Capacity { get { return capacity; } }
    /// <summary>残り容量</summary>
    private List<decimal> free;
    /// <summary>ビン数</summary>
    public int NumBins { get { return free.Count == 0 ? 0 : free.Count / 2 + 1; } }
    /// <summary>コンストラクタ</summary>
    public BinSet(decimal capa)
    {
        capacity = capa;
        Reset();
    }
    /// <summary>リセット</summary>
    public void Reset()
    {
        free = new List<decimal>(14);
    }
    /// <summary>追加</summary>
    public void Insert(decimal d)
    {
        if (d == 0) return;
        if (d < 0) throw new ArgumentException("Out of range");
        while (d > capacity)
        {
            Insert(capacity);
            d -= capacity;
        }
        int k = free.Count, kk = 0;
        if (k == 0 || (d > free[0] && (k == 1 || d > free[1])))
        {
            if (k > 1) free.Add(free[k / 2 - 1]);
            free.Add(capacity - d);
        }
        else
        {
            while (kk < free.Count)
            {
                if (d <= free[kk] || ++kk < free.Count)
                {
                    k = kk;
                    kk = k * 2 + 2;
                }
            }
            free[k] -= d;
        }
        while (k > 1)
        {
            k = k / 2 - 1;
            free[k] = Math.Max(free[k * 2 + 2], free[k * 2 + 3]);
        }
    }
    /// <summary>文字列</summary>
    public override string ToString()
    {
        System.Text.StringBuilder sb = new System.Text.StringBuilder();
        for (int i = free.Count - NumBins; i < free.Count; ++i) sb.Append(free[i] + " ");
        return sb.ToString();
    }
    /// <summary>テスト</summary>
    public static void Main()
    {
        BinSet bs = new BinSet(1);
        for (int i = 0; i < 20; ++i)
        {
            bs.Insert((i * 0.1M) % 0.5M + 0.1M);
            Console.WriteLine("{0} ({1})", bs.NumBins, bs);
        }
    }
}