情報学部 菅沼ホーム 目次 索引

最適化（動的計画法）

    1. A. C++
    2. B. Java
    3. C. JavaScript
    4. D. PHP
    5. E. Ruby
    6. F. Python
    7. G. C#
    8. H. VB

　　プログラムは，動的計画法を使用して，資源配分問題を解くためのものです．

  1. C++ 

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

/**********************************/
/* 動的計画法（ナップサック問題） */
/*      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;
}

/*****************************************/
/* 動的計画法によるナップサック問題      */
/*      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;
}

  2. Java 

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

/**********************************/
/* 動的計画法（ナップサック問題） */
/*      coded by Y.Suganuma       */
/**********************************/
import java.io.*;
import java.util.*;

public class Test {
	public static void main(String args[]) throws IOException
	{
		int i1, i2, k, n_toshi, step, n_case, table[][], rieki[][], next[][], max;
		StringTokenizer str;
		String line;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
					// データの入力
							// 1 行目
		line = in.readLine();
		str  = new StringTokenizer(line, " ");
		line = str.nextToken();
		line = str.nextToken();
		n_toshi = Integer.parseInt(line);
		line = str.nextToken();
		line = str.nextToken();
		step = Integer.parseInt(line);
		line = str.nextToken();
		line = str.nextToken();
		n_case = Integer.parseInt(line);
		table = new int [n_toshi][n_case];
		rieki = new int [n_toshi][n_case];
		next  = new int [n_toshi][n_case];
							// 2 行目
		line = in.readLine();
							// 3 行目以降
		for (i1 = 0; i1 < n_toshi; i1++) {
			line = in.readLine();
			str  = new StringTokenizer(line, " ");
			line = str.nextToken();
			for (i2 = 0; i2 < n_case; i2++) {
				line = str.nextToken();
				table[i1][i2] = Integer.parseInt(line);
			}
		}
					// 実行
		max = 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("解が存在しません！");
	}

	/*****************************************/
	/* 動的計画法によるナップサック問題      */
	/*      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;
	}
}

  3. JavaScript

    　　ここをクリックして表示された画面においてデータを設定し，「 実行 」ボタンをクリックすれば画面上で実行可能です． 

    <!DOCTYPE HTML>

<HTML>

<HEAD>

	<TITLE>動的計画法（ナップサック問題）</TITLE>
	<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8">
	<SCRIPT TYPE="text/javascript">
		res = "";
		/****************/
		/* main program */
		/****************/
		function main()
		{
					// データの入力
							// 1 行目
			let lines   = (document.getElementById("data").value).split('\n');
			let str     = lines[0].split(' ').filter(function(e){return e.length > 0;});
			let n_toshi = parseInt(str[1]);
			let step    = parseInt(str[3]);
			let n_case  = parseInt(str[5]);
			let table   = new Array(n_toshi);
			let rieki   = new Array(n_toshi);
			let next    = new Array(n_toshi);
			for (let i1 = 0; i1 < n_toshi; i1++) {
				table[i1] = new Array(n_case);
				rieki[i1] = new Array(n_case);
				next[i1]  = new Array(n_case);
			}
							// 3 行目以降
			for (let i1 = 0; i1 < n_toshi; i1++) {
				str = lines[i1+2].split(' ').filter(function(e){return e.length > 0;});
				for (let i2 = 0; i2 < n_case; i2++)
					table[i1][i2] = parseInt(str[i2+1]);
			}
					// 実行
			let max = dynamic(0, n_toshi, step, n_case, table, rieki, next);
					// 結果の出力
			if (max >= 0) {
				res += ("最大利益 " + rieki[n_toshi-1][max] + "\n");
				for (let i1 = n_toshi-1; i1 >= 0; i1--) {
					let k = max * step;
					if (i1 > 0) {
						max  = next[i1][max];
						k   -= max * step;
					}
					res += ("   投資先 " + (i1+1) + " 投資資金 " + k + "\n");
				}
			}
			else
				res = "解が存在しません！";
			document.getElementById("result").value = res;
		}

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

			return m;
		}
	</SCRIPT>

</HEAD>

<BODY STYLE="font-size: 130%; text-align:center; background-color: #eeffee;">

	<H2><B>動的計画法（ナップサック問題）</B></H2>

	<BUTTON STYLE="font-size: 100%; background-color: pink" onClick="return main()">実行</BUTTON><BR>
	<DIV STYLE="width: 800px; margin-right: auto; margin-left: auto">
		<DIV STYLE="text-align:center; float: right; width: 400px">
			<DIV STYLE="text-align:center">結果</DIV>
			<TEXTAREA ID="result" COLS="35" ROWS="10" STYLE="font-size: 100%; width: 380px">
			</TEXTAREA>
		</DIV>
		<DIV STYLE="text-align:center; width: 400px">
			<DIV STYLE="text-align:center">データ</DIV>
			<TEXTAREA ID="data" COLS="35" ROWS="10" STYLE="font-size: 100%; width: 380px">
投資先 3 投資単位 1 ケース数 5
以下，各投資先に資金を投資した場合の利益を入力（ケース数だけ入力）
投資先１ 0 8 18 22 24
投資先２ 0 3 6 9 12
投資先３ 0 6 7 8 10
			</TEXTAREA>
		</DIV>
	</DIV>
</BODY>

</HTML>

  4. PHP 

    <?php

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

/**********************************/
/* 動的計画法（ナップサック問題） */
/*      coded by Y.Suganuma       */
/**********************************/

					// データの入力と領域の確保
	fscanf(STDIN, "%*s %d %*s %d %*s %d", $n_toshi, $step, $n_case);

	$table = array($n_toshi);
	$rieki = array($n_toshi);
	$next  = array($n_toshi);
	for ($i1 = 0; $i1 < $n_toshi; $i1++) {
		$table[$i1] = array($n_case);
		$rieki[$i1] = array($n_case);
		$next[$i1]  = array($n_case);
	}

	fgets(STDIN);
	for ($i1 = 0; $i1 < $n_toshi; $i1++) {
		$str = trim(fgets(STDIN));
		strtok($str, " ");
		for ($i2 = 0; $i2 < $n_case; $i2++)
			$table[$i1][$i2] = intval(strtok(" "));
	}
					// 実行
	$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");

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

?>

  5. Ruby 

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

#*********************************/
# 動的計画法（ナップサック問題） */
#      coded by Y.Suganuma       */
#*********************************/

#****************************************/
# 動的計画法によるナップサック問題      */
#      p : 現在計算中の投資先           */
#      n_toshi : 投資先の数             */
#      step : 資金の投資単位            */
#      n_case : 資金の投資ケース数      */
#      table : 投資先，投資金額毎の利益 */
#      rieki : 現段階の最大利益（φ）   */
#      nxt : 最大利益を与える投資先     */
#      coded by Y.Suganuma              */
#****************************************/
def dynamic(p, n_toshi, step, n_case, table, rieki, nxt)

	m = 0
					# 最大利益の計算
						# １段目
	if p == 0
		for i1 in 0 ... n_case
			rieki[p][i1] = table[p][i1]
		end
						# ２段目以降
	else
		for i1 in 0 ... n_case
			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
					end
					m2 += step
					k2 += 1
				end
				m1 += step
				k1 += 1
			end
			nxt[p][i1] = l2
			if l2 >= 0
				rieki[p][i1] = table[p][l1] + rieki[p-1][l2]
			end
		end
	end
					# 次の投資先
						# 最終段より前
	if p < n_toshi-1
		m = dynamic(p+1, n_toshi, step, n_case, table, rieki, nxt)
						# 最終段
	else
		max = -1
		k1  = n_toshi - 1
		for i1 in 0 ... n_case
			if nxt[k1][i1] >= 0 && rieki[k1][i1] > max
				max = rieki[k1][i1]
				m   = i1
			end
		end
	end

	return m
end

				# データの入力と領域の確保
str     = gets()
a       = str.split(" ")
n_toshi = Integer(a[1])
step    = Integer(a[3])
n_case  = Integer(a[5])
str     = gets()
table   = Array.new(n_toshi)
rieki   = Array.new(n_toshi)
nxt     = Array.new(n_toshi)
for i1 in 0 ... n_toshi
	table[i1] = Array.new(n_case)
	rieki[i1] = Array.new(n_case)
	nxt[i1]   = Array.new(n_case)
end
for i1 in 0 ... n_toshi
	str = gets()
	a   = str.split(" ")
	for i2 in 0 ... n_case
		table[i1][i2] = Integer(a[i2+1])
	end
end
				# 実行
max = dynamic(0, n_toshi, step, n_case, table, rieki, nxt)
				# 結果の出力
if max >= 0
	printf("最大利益 %d\n", rieki[n_toshi-1][max])
	i1 = n_toshi-1
	while i1 >= 0
		k = max * step
		if i1 > 0
			max  = nxt[i1][max]
			k   -= max * step
		end
		printf("   投資先 %d 投資資金 %d\n", i1+1, k)
		i1 -= 1
	end
else
	printf("解が存在しません！\n")
end

  6. Python 

    # -*- coding: UTF-8 -*-
import numpy as np
import sys
from math import *

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

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

def dynamic(p, n_toshi, step, n_case, table, rieki, next) :

	m = 0
			# 最大利益の計算
				# １段目
	if p == 0 :
		for i1 in range(0, n_case) :
			rieki[p][i1] = table[p][i1]
				# ２段目以降
	else :
		for i1 in range(0, n_case) :
			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 += 1
				m1 += step
				k1 += 1
			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 in range(0, n_case) :
			if next[k1][i1] >= 0 and rieki[k1][i1] > max :
				max = rieki[k1][i1]
				m   = i1

	return m

############################################
# 動的計画法（ナップサック問題）
#      coded by Y.Suganuma
############################################

			# データの入力
line    = sys.stdin.readline()
s       = line.split()
n_toshi = int(s[1])
step    = int(s[3])
n_case  = int(s[5])

line    = sys.stdin.readline()

table   = np.empty((n_toshi, n_case), np.int)
rieki   = np.empty((n_toshi, n_case), np.int)
next    = np.empty((n_toshi, n_case), np.int)
for i1 in range(0, n_toshi) :
	line = sys.stdin.readline()
	s    = line.split()
	for i2 in range(0, n_case) :
		table[i1][i2] = int(s[i2+1])
			# 実行
max = dynamic(0, n_toshi, step, n_case, table, rieki, next)
			# 結果の出力
if max >= 0 :
	print("最大利益 " + str(rieki[n_toshi-1][max]))
	for i1 in range(n_toshi-1, -1, -1) :
		k = max * step
		if i1 > 0 :
			max  = next[i1][max]
			k   -= max * step
		print("   投資先 " + str(i1+1) + " 投資資金 " + str(k))
else :
	print("解が存在しません！")

  7. C# 

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

/**********************************/
/* 動的計画法（ナップサック問題） */
/*      coded by Y.Suganuma       */
/**********************************/
using System;

class Program
{
	static void Main()
	{
		Test1 ts = new Test1();
	}
}

class Test1
{
	public Test1()
	{
					// データの入力
							// 1 行目
		string[] str  = Console.ReadLine().Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
		int n_toshi   = int.Parse(str[1]);
		int step      = int.Parse(str[3]);
		int n_case    = int.Parse(str[5]);
		int[][] table = new int [n_toshi][];
		int[][] rieki = new int [n_toshi][];
		int[][] next  = new int [n_toshi][];
		for (int i1 = 0; i1 < n_toshi; i1++) {
			table[i1] = new int [n_case];
			rieki[i1] = new int [n_case];
			next[i1]  = new int [n_case];
		}
							// 2 行目
		Console.ReadLine();
							// 3 行目以降
		for (int i1 = 0; i1 < n_toshi; i1++) {
			str = Console.ReadLine().Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
			for (int i2 = 0; i2 < n_case; i2++)
				table[i1][i2] = int.Parse(str[i2+1]);
		}
					// 実行
		int max = dynamic(0, n_toshi, step, n_case, table, rieki, next);
					// 結果の出力
		if (max >= 0) {
			Console.WriteLine("最大利益 " + rieki[n_toshi-1][max]);
			for (int i1 = n_toshi-1; i1 >= 0; i1--) {
				int k = max * step;
				if (i1 > 0) {
					max  = next[i1][max];
					k   -= max * step;
				}
				Console.WriteLine("   投資先 " + (i1+1) + " 投資資金 " + k);
			}
		}
		else
			Console.WriteLine("解が存在しません！");
	}

	/*****************************************/
	/* 動的計画法によるナップサック問題      */
	/*      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 m = 0;
						// １段目
		if (p == 0) {
			for (int i1 = 0; i1 < n_case; i1++)
				rieki[p][i1] = table[p][i1];
		}
						// ２段目以降
		else {
			for (int i1 = 0; i1 < n_case; i1++) {
				int l1  = -1;
				int l2  = -1;
				int max = -1;
				int m1  = 0;
				int k1  = 0;
				m        = step * i1;
				while (m1 <= m) {
					int m2 = 0;
					int k2 = 0;
					while (m1+m2 <= m) {
						int 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 {
			int max = -1;
			int k1  = n_toshi - 1;
			for (int i1 = 0; i1 < n_case; i1++) {
				if (next[k1][i1] >= 0 && rieki[k1][i1] > max) {
					max = rieki[k1][i1];
					m   = i1;
				}
			}
		}

		return m;
	}
}

  8. VB 

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

''''''''''''''''''''''''''''''''''
' 動的計画法（ナップサック問題） '
'      coded by Y.Suganuma       '
''''''''''''''''''''''''''''''''''
Imports System.Text.RegularExpressions

Module Test

	Sub Main()
					' データの入力
							' 1 行目
		Dim MS As Regex        = New Regex("\s+") 
		Dim str() As String    = MS.Split(Console.ReadLine().Trim())
		Dim n_toshi As Integer = Integer.Parse(str(1))
		Dim step1 As Integer   = Integer.Parse(str(3))
		Dim n_case As Integer  = Integer.Parse(str(5))
		Dim table(n_toshi,n_case) As Integer
		Dim rieki(n_toshi,n_case) As Integer
		Dim nxt(n_toshi,n_case) As Integer
							' 2 行目
		Console.ReadLine()
							' 3 行目以降
		For i1 As Integer = 0 To n_toshi-1
			str = MS.Split(Console.ReadLine().Trim())
			For i2 As Integer = 0 To n_case-1
				table(i1,i2) = Integer.Parse(str(i2+1))
			Next
		Next
					' 実行
		Dim max As Integer = dynamic(0, n_toshi, step1, n_case, table, rieki, nxt)
					' 結果の出力
		If max >= 0
			Console.WriteLine("最大利益 " & rieki(n_toshi-1,max))
			For i1 As Integer = n_toshi-1 To 0 step -1
				Dim k As Integer = max * step1
				If i1 > 0
					max  = nxt(i1,max)
					k   -= max * step1
				End If
				Console.WriteLine("   投資先 " & (i1+1) & " 投資資金 " & k)
			Next
		Else
			Console.WriteLine("解が存在しません！")
		End If

	End Sub

	'''''''''''''''''''''''''''''''''''''''''
	' 動的計画法によるナップサック問題      '
	'      p : 現在計算中の投資先           '
	'      n_toshi : 投資先の数             '
	'      step1 : 資金の投資単位           '
	'      n_case : 資金の投資ケース数      '
	'      table : 投資先，投資金額毎の利益 '
	'      rieki : 現段階の最大利益（φ）   '
	'      nxt : 最大利益を与える投資先     '
	'      coded by Y.Suganuma              '
	'''''''''''''''''''''''''''''''''''''''''
	Function dynamic(p As Integer, n_toshi As Integer, step1 As Integer,
	                 n_case As Integer, table(,) As Integer, rieki(,) As Integer,
	                 nxt(,) As Integer)

					' 最大利益の計算
		Dim m As Integer = 0
						' １段目
		If p = 0
			For i1 As Integer = 0 To n_case-1
				rieki(p,i1) = table(p,i1)
			Next
						' ２段目以降
		Else
			For i1 As Integer = 0 To n_case-1
				Dim l1 As Integer  = -1
				Dim l2 As Integer  = -1
				Dim max As Integer = -1
				Dim m1 As Integer  = 0
				Dim k1 As Integer  = 0
				m = step1 * i1
				Do While m1 <= m
					Dim m2 As Integer = 0
					Dim k2 As Integer = 0
					Do While m1+m2 <= m
						Dim r As Integer = table(p,k1) + rieki(p-1,k2)
						If r > max
							l1  = k1
							l2  = k2
							max = r
						End If
						m2 += step1
						k2 += 1
					Loop
					m1 += step1
					k1 += 1
				Loop
				nxt(p,i1) = l2
				If l2 >= 0
					rieki(p,i1) = table(p,l1) + rieki(p-1,l2)
				End If
			Next
		End If
					' 次の投資先
						' 最終段より前
		If p < n_toshi-1
			m = dynamic(p+1, n_toshi, step1, n_case, table, rieki, nxt)
						' 最終段
		Else
			Dim max As Integer = -1
			Dim k1 As Integer  = n_toshi - 1
			For i1 As Integer = 0 To n_case-1
				If nxt(k1,i1) >= 0 and rieki(k1,i1) > max
					max = rieki(k1,i1)
					m   = i1
				End If
			Next
		End If

		Return m

	End Function

End Module

情報学部 菅沼ホーム 目次 索引