動的計画法（ロットサイズ決定問題）

-------------------------i_data-------------------------
期の数 6 段取り費 200 在庫保持費用 1
各期の需要 40 35 50 20 30 35
各期の製造単価 10 10 10 10 10 10

-----------------------program-------------------------
/**************************************/
/* 動的計画法（ロットサイズ決定問題） */
/*      coded by Y.Suganuma           */
/**************************************/
#include <stdio.h>

void dynamic(int, int, int, int, int, int *, int *, int **, int **);

int main()
{
	int i1, h, K, k0, k1 = 0, k2 = 0, n_ki, n_case = 1, *juyou, *seizo, **hiyou, **next;
					// データの入力と領域の確保
	scanf("%*s %d %*s %d %*s %d", &n_ki, &K, &h);
	juyou = new int [n_ki];
	seizo = new int [n_ki];

	scanf("%*s");
	for (i1 = 0; i1 < n_ki; i1++) {
		scanf("%d", &juyou[i1]);
		n_case += juyou[i1];
	}

	scanf("%*s");
	for (i1 = 0; i1 < n_ki; i1++)
		scanf("%d", &seizo[i1]);

	hiyou = new int * [n_ki];
	next  = new int * [n_ki];
	for (i1 = 0; i1 < n_ki; i1++) {
		hiyou[i1] = new int [n_case];
		next[i1]  = new int [n_case];
	}
					// 実行
	dynamic(0, n_ki, n_case, K, h, juyou, seizo, hiyou, next);
					// 結果の出力
	k0 = n_case - 1;
	if (hiyou[n_ki-1][k0] >= 0) {
		for (i1 = n_ki-1; i1 >= 0; i1--) {
			if (i1 < n_ki-1)
				printf(" 今期の生産量 %d 今期の費用 %d\n", k2-k0, k1-hiyou[i1][k0]);
			printf("%d 期： 総費用 %d", i1+1, hiyou[i1][k0]);
			if (i1 == 0)
				printf(" 今期の生産量 %d 今期の費用 %d\n", k0, hiyou[i1][k0]);
			if (i1 != 0) {
				k1 = hiyou[i1][k0];
				k2 = k0;
				k0 = next[i1][k0];
			}
		}
	}
	else
		printf("解が存在しません！\n");
					// 領域の開放
	for (i1 = 0; i1 < n_ki; i1++) {
		delete [] hiyou[i1];
		delete [] next[i1];
	}
	delete [] hiyou;
	delete [] next;
	delete [] juyou;
	delete [] seizo;

	return 0;
}

/****************************************/
/* 動的計画法によるロットサイズ決定問題 */
/*      p : 現在の期                    */
/*      n_ki : 期の数                   */
/*      n_case : 総需要+1               */
/*      K : 段取り費                    */
/*      h : 在庫保持費用                */
/*      juyou : 各期の需要              */
/*      seizo : 各期の製造単価          */
/*      hiyou : 現段階の最小費用（φ）  */
/*      next : 前期の対応する最小費用   */
/*      coded by Y.Suganuma             */
/****************************************/
void dynamic(int p, int n_ki, int n_case, int K, int h,
            int *juyou, int *seizo, int **hiyou, int **next)
{
	int i1, i2, k1, k2, k3, m = 0, min, n_c = 0, v;
					// 最小費用の計算
						// １期目
	if (p == 0) {
		for (i1 = 0; i1 < n_case; i1++) {
			next[p][i1]  = -1;
			hiyou[p][i1] = -1;
		}
		for (i1 = juyou[0]; i1 < n_case; i1++)
			hiyou[p][i1] = K + i1 * seizo[p];
	}
						// ２期目以降
	else {

		for (i1 = 0; i1 < n_case; i1++) {
			hiyou[p][i1] = -1;
			next[p][i1]  = -1;
		}

		for (i1 = p; i1 < n_ki; i1++)   // 今期以降の総需要
			n_c += juyou[i1];

		k2 = n_case - 1 - n_c;   // 前期までの総需要
		k1 = k2 + juyou[p];   // 今期までの総需要
		for (i1 = k1; i1 < n_case; i1++) {   // i1 : 今期までの総生産量
			min = -1;
			m   = -1;
			for (i2 = 0; i1-i2 >= k2; i2++) {   // i2 : 今期の生産量
				k3  = i1 - i2;
				v   = (i2 == 0) ? 0 : K + i2 * seizo[p];   // 今期の製造費
				v  += hiyou[p-1][k3];   // 前期までの総費用
				v  += h * (k3 - k2);   // 在庫維持費
				if (min < 0 || min >= 0 && v < min) {
					min = v;
					m   = k3;
				}
			}
			next[p][i1] = m;
			if (m >= 0)
				hiyou[p][i1] = min;
		}
	}
					// 次の期
	if (p < n_ki-1)
		dynamic(p+1, n_ki, n_case, K, h, juyou, seizo, hiyou, next);
}