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

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

------------------------program------------------------
/**************************************/
/* 動的計画法（ロットサイズ決定問題） */
/*      coded by Y.Suganuma           */
/**************************************/
import java.io.*;
import java.util.StringTokenizer;

class Test {
	public static void main(String args[]) throws IOException
	{
		int i1, h, K, k0, k1 = 0, k2 = 0, n_ki, n_case = 1, juyou[], seizo[], hiyou[][], next[][];
		String str;
		StringTokenizer dt;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
					// データの入力と領域の確保
		str = in.readLine();
		dt  = new StringTokenizer(str, " ");
		dt.nextToken();
		n_ki = Integer.parseInt(dt.nextToken());
		dt.nextToken();
		K = Integer.parseInt(dt.nextToken());
		dt.nextToken();
		h = Integer.parseInt(dt.nextToken());
		juyou = new int [n_ki];
		seizo = new int [n_ki];

		str = in.readLine();
		dt  = new StringTokenizer(str, " ");
		dt.nextToken();
		for (i1 = 0; i1 < n_ki; i1++) {
			juyou[i1]  = Integer.parseInt(dt.nextToken());
			n_case    += juyou[i1];
		}

		str = in.readLine();
		dt  = new StringTokenizer(str, " ");
		dt.nextToken();
		for (i1 = 0; i1 < n_ki; i1++)
			seizo[i1]  = Integer.parseInt(dt.nextToken());

		hiyou = new int [n_ki][n_case];
		next  = new int [n_ki][n_case];
					// 実行
		App.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)
					System.out.println(" 今期の生産量 " + (k2-k0) +
                                       " 今期の費用 " + (k1-hiyou[i1][k0]));
				System.out.print((i1+1) + " 期： 総費用 " + hiyou[i1][k0]);
				if (i1 == 0)
					System.out.println(" 今期の生産量 " + k0 + " 今期の費用 " + hiyou[i1][k0]);
				if (i1 != 0) {
					k1 = hiyou[i1][k0];
					k2 = k0;
					k0 = next[i1][k0];
				}
			}
		}
		else
			System.out.println("解が存在しません！");
	}
}

/************************
/* 科学技術系算用の手法 */
/************************/
class App {

	/****************************************/
	/* 動的計画法によるロットサイズ決定問題 */
	/*      p : 現在の期                    */
	/*      n_ki : 期の数                   */
	/*      n_case : 総需要+1               */
	/*      K : 段取り費                    */
	/*      h : 在庫保持費用                */
	/*      juyou : 各期の需要              */
	/*      seizo : 各期の製造単価          */
	/*      hiyou : 現段階の最小費用（φ）  */
	/*      next : 前期の対応する最小費用   */
	/*      coded by Y.Suganuma             */
	/****************************************/
	static 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)
			App.dynamic(p+1, n_ki, n_case, K, h, juyou, seizo, hiyou, next);
	}
}