静岡理工科大学 菅沼ホーム 目次 索引

最適化(動的計画法)

    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
    以下,各投資先に資金を投資した場合の利益を入力(ケース数だけ入力)
    投資先1 0 8 18 22 24
    投資先2 0 3 6 9 12
    投資先3 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;
    					// 最大利益の計算
    						// 1段目
    	if (p == 0) {
    		for (i1 = 0; i1 < n_case; i1++)
    			rieki[p][i1] = table[p][i1];
    	}
    						// 2段目以降
    	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
    以下,各投資先に資金を投資した場合の利益を入力(ケース数だけ入力)
    投資先1 0 8 18 22 24
    投資先2 0 3 6 9 12
    投資先3 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;
    					// 最大利益の計算
    						// 1段目
    		if (p == 0) {
    			for (i1 = 0; i1 < n_case; i1++)
    				rieki[p][i1] = table[p][i1];
    		}
    						// 2段目以降
    		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;
    						// 1段目
    			if (p == 0) {
    				for (let i1 = 0; i1 < n_case; i1++)
    					rieki[p][i1] = table[p][i1];
    			}
    						// 2段目以降
    			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
    以下,各投資先に資金を投資した場合の利益を入力(ケース数だけ入力)
    投資先1 0 8 18 22 24
    投資先2 0 3 6 9 12
    投資先3 0 6 7 8 10
    			</TEXTAREA>
    		</DIV>
    	</DIV>
    </BODY>
    
    </HTML>
    			

  4. PHP

    <?php
    
    /* データ例
    投資先 3 投資単位 1 ケース数 5
    以下,各投資先に資金を投資した場合の利益を入力(ケース数だけ入力)
    投資先1 0 8 18 22 24
    投資先2 0 3 6 9 12
    投資先3 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;
    					// 最大利益の計算
    						// 1段目
    	if ($p == 0) {
    		for ($i1 = 0; $i1 < $n_case; $i1++)
    			$rieki[$p][$i1] = $table[$p][$i1];
    	}
    						// 2段目以降
    	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
    以下,各投資先に資金を投資した場合の利益を入力(ケース数だけ入力)
    投資先1 0 8 18 22 24
    投資先2 0 3 6 9 12
    投資先3 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
    					# 最大利益の計算
    						# 1段目
    	if p == 0
    		for i1 in 0 ... n_case
    			rieki[p][i1] = table[p][i1]
    		end
    						# 2段目以降
    	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
    以下,各投資先に資金を投資した場合の利益を入力(ケース数だけ入力)
    投資先1 0 8 18 22 24
    投資先2 0 3 6 9 12
    投資先3 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
    			# 最大利益の計算
    				# 1段目
    	if p == 0 :
    		for i1 in range(0, n_case) :
    			rieki[p][i1] = table[p][i1]
    				# 2段目以降
    	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
    以下,各投資先に資金を投資した場合の利益を入力(ケース数だけ入力)
    投資先1 0 8 18 22 24
    投資先2 0 3 6 9 12
    投資先3 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;
    						// 1段目
    		if (p == 0) {
    			for (int i1 = 0; i1 < n_case; i1++)
    				rieki[p][i1] = table[p][i1];
    		}
    						// 2段目以降
    		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
    以下,各投資先に資金を投資した場合の利益を入力(ケース数だけ入力)
    投資先1 0 8 18 22 24
    投資先2 0 3 6 9 12
    投資先3 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
    						' 1段目
    		If p = 0
    			For i1 As Integer = 0 To n_case-1
    				rieki(p,i1) = table(p,i1)
    			Next
    						' 2段目以降
    		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
    			

静岡理工科大学 菅沼ホーム 目次 索引