読者です 読者をやめる 読者になる 読者になる

素人がプログラミングを勉強していたブログ

プログラミング、セキュリティ、英語、Webなどのブログ since 2008

連絡先: すかいぷ:javascripter_  か javascripter あっと tsukkun.net skypeのほうがいいです

足し算引き算で10を作るゲームと部分和問題、DP

javascript

切符の問題

切符の裏に印刷してある4桁の数字を4つの数字と考えて、足し算と引き算だけで10を作るゲームの解き方。
例えば、1,2,3,4の場合は1+2+3+4=10。

プログラム的には、

prob([1,2,3,4]); // [{plus: [1,2,3,4], minus: []}]

こんな感じに返ってくるようにしたい。

まず、2,4,5,7から10を作る場合。2+4+5+7=18であるので、上記の式のいくつかの符号を-にすればいいことが分かる。一つの数字を引くと、18を出す時に最初に足した分と、今引こうとしている分の2つ引かなければならないから、逆算して、(18-10)/2=4を引けばいいと分かる。
この場合、合計が4になる組合せは、4そのものしかないから、2-4+5+7=10、が答えと分かる。

(合計-10)/2が引く数の合計で、それ以外が足す数である。2で割っているので、全部の数字の合計が奇数の場合はそもそも作れない。

+-で10を作る問題は、引く数の和をつくる部分和問題に分解できるとわかった。

部分和問題

1,2,3,4から7を作る場合。まず、何もない状態の合計は0。1を作る方法は1だ。2は、2だ。3は、1+2と、3がある。4は、4と1+3だ。
5は、1+4と、2+3と、5だ。
6は、1+2 + 3と、2+4だ。1+2+3のところで、3を作った時の1+2の式が使われているとわかる。
7は、1+2+4、3+4。3+4で、(1+2)+4と(3)+4になる。
大きな数は、小さな数を組合せていけばいいと分かった。

プログラム的には、

subset_sum([1,2,3,4], 7); // [[1,2,4], [3, 4]]]

と表現することにする。

var subset_sum = function (nums, sum) {
  var dp = [];
  var i, j, k;
  for (i = 0; i <= nums.length; i++) {
    dp[i] = [];
    for (j = 0; j <= sum; j++) {
      dp[i][j] = [];
    }
  }

まず、numsと同じ長さの三次元配列を作る。個々の配列は0からsumまであって、その中身は空の配列にする。
dp[numsの先頭からx個][目標の数y]に、使う数字の配列を置く。

  dp[0][0].push([]);

0は空配列の合計と考えるので、dp[0][0].push([]);した。
残りの部分。

  for (i = 0; i < dp.length - 1; i++) {
    for (j = 0; j < dp[i].length; j++) {
      for (k = 0; k < dp[i][j].length; k++) {
	// 次の数i+1で、j(0からsumのあいだ)を作る
	// 前の数iで出来たら必ずできるのでpushする
	if (nums.indexOf(nums[i], i + 1) <= 0) { // numsが重複してても1回しかpushしない
	  dp[i + 1][j].push(dp[i][j][k]);
	}
	// それから、j+nums[i]が<=sumの場合、i+1まででj+nums[i]が作れるので
        if (j + nums[i] <= sum) {
        // 前の数の配列+次の数、を記録しておく。
          dp[i + 1][j + nums[i]].push(dp[i][j][k].concat(nums[i]));
        }
      }
    }
  }
  // 最終的に、dp.length - 1 == nums.length -1までで、sumを作る答えを返す
  return dp[nums.length-1][sum];
};

ふう、できた。

完成

切符で10を作る問題だったので、その部分も作る。

var subset_sum = function (nums, sum) {
  var dp = [];
  var i, j, k;
  for (i = 0; i <= nums.length; i++) {
    dp[i] = [];
    for (j = 0; j <= sum; j++) {
      dp[i][j] = [];
    }
  }
  dp[0][0].push([]);

  for (i = 0; i < dp.length - 1; i++) {
    for (j = 0; j < dp[i].length; j++) {
      for (k = 0; k < dp[i][j].length; k++) {
	if (nums.indexOf(nums[i], i + 1) <= 0) { // numsが重複してても1回しかpushしない
          dp[i + 1][j].push(dp[i][j][k]);
	}
        if (j + nums[i] <= sum) {
          dp[i + 1][j + nums[i]].push(dp[i][j][k].concat(nums[i]));
        }
      }
    }
  }
  return dp[nums.length - 1][sum];
};

var prob = function (nums) {
  var exclude = function (a, b) { // 配列の引き算
    a = a.concat();
    var i, n;
    for (i = 0; i < b.length; i++) {
      n = a.indexOf(b[i]);
      if (n >= 0) {
        a.splice(n, 1);
      }
    }
    return a;
  };

  var i, j, k, total = 0, tmp;
  var results = [];
  for (i = 0; i < nums.length; i++) {
    total += nums[i];
  }
  if (total % 2 != 0) {
    // 奇数の場合は作れない
    return [];
  }
  tmp = subset_sum(nums, (total - 10) / 2); // 引く数
  for (i = 0; i < tmp.length; i++) {
    results[i] = {
      plus: exclude(nums, tmp[i]), // 引く数以外が足す数
      minus: tmp[i]
    };
  }
  return results;
};

確認する。

prob([1,2,3,4]); // [{plus:[1,2,3,4],minus:[]}]
prob([2,3,5,6]); // [{plus:[2,5,6],minus:[3]}]
prob([0,1,2,7]); // [{plus:[0,1,2,7],minus:[]},{plus:[1,2,7],minus:[0]}]

おし、できてるっぽい。

感想

DPの解き方およびコードの見本はqnighy(只者ではない男)から教えてもらった。id:qnighy ++。