-------------------------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       */
/**************************************/
import java.io.*;

public class Test {
	public static void main(String args[]) throws IOException
	{
		int i1, i2, k, n_toshi, step, n_case, table[][], rieki[][], next[][], max;
		String str;
		Data dt;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
					// データの入力
		str = in.readLine();
		dt  = new Data(str);
		dt.next();
		dt.next();
		n_toshi = Integer.parseInt(dt.data);
		dt.next();
		dt.next();
		step = Integer.parseInt(dt.data);
		dt.next();
		dt.next();
		n_case = Integer.parseInt(dt.data);
		table = new int [n_toshi][n_case];
		rieki = new int [n_toshi][n_case];
		next  = new int [n_toshi][n_case];

		str = in.readLine();

		for (i1 = 0; i1 < n_toshi; i1++) {
			str = in.readLine();
			dt  = new Data(str);
			dt.next();
			for (i2 = 0; i2 < n_case; i2++) {
				dt.next();
				table[i1][i2] = Integer.parseInt(dt.data);
			}
		}
					// 実行
		max = App.dynamic(0, n_toshi, step, n_case, table, rieki, next);
					// 結果の出力
		if (max >= 0) {
			System.out.println("最大利益 " + 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;
				}
				System.out.println("   投資先 " + (i1+1) + " 投資資金 " + k);
			}
		}
		else
			System.out.println("解が存在しません！");
	}
}

-------------------------App.java-------------------------
/****************************
/*     科学技術系算用の手法 */
/****************************/
public class App {

	/*********************************************/
	/*     動的計画法によるナップサック問題      */
	/*          p : 現在計算中の投資先           */
	/*          n_toshi : 投資先の数             */
	/*          step : 資金の投資単位            */
	/*          n_case : 資金の投資ケース数      */
	/*          table : 投資先，投資金額毎の利益 */
	/*          rieki : 現段階の最大利益（φ）   */
	/*          next : 最大利益を与える投資先    */
	/*          coded by Y.Suganuma              */
	/*********************************************/
	static 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;
	}
}

-------------------------Data.java-------------------------
/**********************************************/
/*     １行のデータから個々のデータを取り出す */
/*          coded by Y.Suganuma               */
/**********************************************/
public class Data {

	private int len, start, end;
	private String line;
	String data;
					// コンストラクタ
	Data (String l)
	{
		line  = l;
		len   = line.length();
		start = 0;
		end   = 0;
		data  = new String ();   // 次のデータ
	}
					// 次のデータの取り出し
					//   =0 : 成功，=-1 : 失敗
	int next()
	{
		int k = 0;
		if (start < len) {
			int sw = 0;
			while (sw == 0) {
				end = line.indexOf(" ", start);
				if (end >= 0) {
					if ((end - start) > 0) {
						data  = line.substring(start, end);
						sw    = 1;
					}
				}
				else {
					end = len;
					sw  = 1;
					if ((end - start) > 0)
						data  = line.substring(start, end);
					else
						k = -1;
				}
				start = end + 1;
			}
		}
		else
			k = -1;
		return k;
	}
}