ある遺言執行 - 組み合わせの生成の解法例

まず、どう解くかのアルゴリズムを考えないといけませんが、私は次のように考え ました。

1. 預金通帳をいくつか拾って篭に入れ、その合計が 12,789,161 円に近いように するとして、
2. 通帳を拾うかどうかは１ビットの情報
3. そのビットを通帳の数だけ並べればすべてのケースが表現できるから、 20 桁の 2 進数のすべてが通帳の選択と 1 対 1 で対応する
4. ならば、0 から 2^20 - 1 (1,028,575) までの 10 進数について、 選んだ通帳の金額の合計を求めて、目標に一番近いものを記録に残そう

というわけで、下記のプログラムになりました。

驚くべきことに、目標値とわずか 9 円差、誤差にして 0.7 ppm という組み合わせ が存在します。

なお、このプログラムの実行時間が PentiumII 400MHz の gcc で 0.84 秒ですが、 今、これを awk に書き換えてみたら、112 秒になりました。となると、始めから awk で書いても、トータルの時間は変わらなかったかもしれません。ビット演算が ありますから、awk のほうが考えにくいということはありますが。

/*
 * 土地と等価な預金の組み合わせ
 *
 * 1999-07-24 K.Hirabayashi
 */

#include <stdio.h>

int x[] = {	/* 預金リスト */
  1113, 1115, 29317, 62769, 146199, 353580, 509388, 753068, 835873,
  1000332, 1001000, 2002272, 2128091, 2443146, 2598946, 2684358,
  3016609, 3489469, 3851663, 8100937, 0
  };

main(argc, argv) char **argv;
{
  int y;

  y = 12789161;	/* 土地の評価額 */
  if (argc > 1)
	y = atoi(argv[1]);
  find(y, x);
  exit(0);
}

find(y, x) int *x;
{
  int i, j, k, m, n, s, t, u;
  int e, err;

  for (n = 0; x[n]; n++)
	;
  if (n >= 32) {
	fprintf(stderr, "預金の口数が多すぎて、プログラムの書き換えが必要。\n");
	exit(1);
  }
  m = (1 << n) - 1;
  for (i = 0; i <= m; i++) {	/* すべての組み合わせを試す */
	s = 0;	/* 篭に入れた預金の合計 */
	for (j = 0, k = 1; j < n; j++, k <<= 1)
		if (i & k)
			s += x[j];
	e = (s < y) ? y - s : s - y;	/* 誤差(絶対値) */
	if (e < err || i == 0) {
		t = s;	/* 現在の預金の合計 */
		u = i;	/* 現在の預金の組み合わせ */
		err = e;	/* 現在の誤差 */
	}
  }
  /* 最良の預金の組み合わせ */
  printf("%d = ", t);
  for (j = i = 0, k = 1; j < n; j++, k <<= 1)
	if (u & k) {
		if (i++ > 0)
			printf("+%d", x[j]);
		else
			printf("%d", x[j]);
	}
  printf("\n");
  printf("誤差 %d 円\n", t - y);
}