動的計画法（メモ化）の研究 その２

その１は
http://d.hatena.ne.jp/kenta11626918/20110524/1306246756から．

問題5：
n種類の数a_iがそれぞれm_i個ずつある．これらの中から，いくつか選び，その総和をちょうどKにすることができるか判定せよ．

再帰で純粋に解いてみる．

//再帰
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 3;
int a[N] = {3, 5, 8};
int m[N] = {3, 2, 2};
const int K = 17;

//最初のi個の中から，和がsumになるものが存在するか？
bool solve(int i, int sum) {
	if(i == 0) {
		if(sum == 0) return true;
	} else {
		int tmp = min(sum/a[i-1], m[i-1]);

		for(int j = 0; j <= tmp; j++) {
			if(solve(i-1, sum-a[i-1]*j)) return true;
		}
	}
	return false;
}


int main() {
	cout << solve(N, K);
}

こんな感じになるんじゃないかな〜とおもう．

これをメモ再帰してみる．

//メモ再帰
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 3;
int a[N] = {3, 5, 8};
int m[N] = {3, 2, 2};
const int K = 17;

//int solve(int i, int sum)に呼応していることに注意．
//bool solveとかくと，警告が発生する．
int memo[N+1][K+1];

void init() {
	memset(memo, -1, sizeof(memo) );
}


//最初のi個の中から，和がsumになるものが存在するか？
//一回でも枝部分のsolve関数でtrueが返されれば，幹のsolve関数はtrueが返る仕組みになっている．
int solve(int i, int sum) {
	if(memo[i][sum] != -1) {
		return memo[i][sum];
	}
	if(i == 0) {
		if(sum == 0) return 1;
	} else {
		int tmp = min(sum/a[i-1], m[i-1]);

		for(int j = 0; j <= tmp; j++) {
			if(solve(i-1, sum-a[i-1]*j) == 1) return 1;
		}
	}
	return memo[i][sum] = 0;
}


int main() {
	init();
	cout << solve(N, K);
}

でも，このプログラムっていろいろ無駄がある．
まず，出力する値は2値，つまり，bool値を返せばいいのに，わざわざintで書かざるを得ないことになっている．
一般にbool値のmemoは無駄なことが多い．もっと情報量を多く持たせるにはどうすればいいだろうか？

もう一回再帰に帰ろう

//再帰
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 3;
int a[N] = {3, 5, 8};
int m[N] = {3, 2, 2};
const int K = 17;

//最初のi個の中から，和がsumにする際，
//もし，和をsumにすることができたら，i番目の数が何個あまっているのか？
//それができなければ-1とする．
//最終的にN個のなかから，和をsumにすることができるか
int solve(int i, int sum) {
	int res;

	//初期条件：
	//最初の0個のなかから，和を0にすることはできるので，0を代入する．
	//一方，最初の0個のなかから，和をsum(>=1)にすることは不可能なので，-1とする．
	if(i == 0) {
		res = ( (sum >= 1) ? -1 : 0);

	//最初のi-1個までにsumにすでに到達している場合，i種類目(配列のインデックス表記じゃない)のものは全く使わなくてよいので，
	//m[i-1]を返す．
	} else if(solve(i-1, sum) != -1) {
		res = m[i-1];

	//無理なときは-1を返す．
	} else if(sum < a[i-1]) {
		res = -1;

	//solve(i, sum-a[i-1])が正の時にかぎり，和をsumにするのに，i種類目のものをもう一つだけ使えばいいので，
	} else {
		int tmp = solve(i, sum-a[i-1]);
		res = ( (tmp <= 0) ? -1 : tmp-1 );
	}
	return res;
}


int main() {
	cout << solve(N, K) << endl;
	return 0;
}