ビンパッキング
先生のところのを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); } } }