-------------------------makefile-------------------------
#
#     リンク
#
CFLAGS = -c -Wall -O2
OBJECT = test.o dynamic.o
pgm: $(OBJECT)
	g++ $(OBJECT) -o test -lm
#
#     コンパイル
#
test.o: test.cpp
	g++ $(CFLAGS) test.cpp
dynamic.o: dynamic.cpp
	g++ $(CFLAGS) dynamic.cpp

-------------------------i_data-------------------------
投資先 3 投資単位 1 ケース数 5
以下，各投資先に資金を投資した場合の利益を入力（ケース数だけ入力）
投資先１ 0 8 18 22 24
投資先２ 0 3 6 9 12
投資先３ 0 6 7 8 10

-------------------------main-------------------------
/**************************************/
/*     動的計画法（ナップサック問題） */
/*          coded by Y.Suganuma       */
/**************************************/
#include <stdio.h>

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

int main()
{
	int i1, i2, k, n_toshi, step, n_case, **table, **rieki, **next, max;
					// データの入力と領域の確保
	scanf("%*s %d %*s %d %*s %d", &n_toshi, &step, &n_case);
	scanf("%*s");
	table = new int * [n_toshi];
	rieki = new int * [n_toshi];
	next  = new int * [n_toshi];
	for (i1 = 0; i1 < n_toshi; i1++) {
		table[i1] = new int [n_case];
		rieki[i1] = new int [n_case];
		next[i1]  = new int [n_case];
	}
	for (i1 = 0; i1 < n_toshi; i1++) {
		scanf("%*s");
		for (i2 = 0; i2 < n_case; i2++)
			scanf("%d", &table[i1][i2]);
	}
					// 実行
	max = dynamic(0, n_toshi, step, n_case, table, rieki, next);
					// 結果の出力
	if (max >= 0) {
		printf("最大利益 %d\n", rieki[n_toshi-1][max]);
		for (i1 = n_toshi-1; i1 >= 0; i1--) {
			k = max * step;
			if (i1 > 0) {
				max  = next[i1][max];
				k   -= max * step;
			}
			printf("   投資先 %d 投資資金 %d\n", i1+1, k);
		}
	}
	else
		printf("解が存在しません！\n");

	return 0;
}

-------------------------dynamic.cpp-------------------------
/*********************************************/
/*     動的計画法によるナップサック問題      */
/*          p : 現在計算中の投資先           */
/*          n_toshi : 投資先の数             */
/*          step : 資金の投資単位            */
/*          n_case : 資金の投資ケース数      */
/*          table : 投資先，投資金額毎の利益 */
/*          rieki : 現段階の最大利益（φ）   */
/*          next : 最大利益を与える投資先    */
/*          coded by Y.Suganuma              */
/*********************************************/
int dynamic(int p, int n_toshi, int step, int n_case, int **table,
             int **rieki, int **next)
{
	int i1, k1, k2, l1, l2, m = 0, m1, m2, max, r;
					// 最大利益の計算
						// １段目
	if (p == 0) {
		for (i1 = 0; i1 < n_case; i1++)
			rieki[p][i1] = table[p][i1];
	}
						// ２段目以降
	else {
		for (i1 = 0; i1 < n_case; i1++) {
			l1  = -1;
			l2  = -1;
			max = -1;
			m   = step * i1;
			m1  = 0;
			k1  = 0;
			while (m1 <= m) {
				m2 = 0;
				k2 = 0;
				while (m1+m2 <= m) {
					r = table[p][k1] + rieki[p-1][k2];
					if (r > max) {
						l1  = k1;
						l2  = k2;
						max = r;
					}
					m2 += step;
					k2++;
				}
				m1 += step;
				k1++;
			}
			next[p][i1] = l2;
			if (l2 >= 0)
				rieki[p][i1] = table[p][l1] + rieki[p-1][l2];
		}
	}
					// 次の投資先
						// 最終段より前
	if (p < n_toshi-1)
		m = dynamic(p+1, n_toshi, step, n_case, table, rieki, next);
						// 最終段
	else {
		max = -1;
		k1  = n_toshi - 1;
		for (i1 = 0; i1 < n_case; i1++) {
			if (next[k1][i1] >= 0 && rieki[k1][i1] > max) {
				max = rieki[k1][i1];
				m   = i1;
			}
		}
	}

	return m;
}