ダイナミックプランニング学習ノート

ある工場は来年A、B、C、Dの4つの新築プロジェクトがあると予想しているが、各プロジェクトの投資額Wkとその投資後の収益Vkは以下の表のように、投資総額は30万元で、どのようにプロジェクトを選んで総収益を最大にすることができるのか.
Project
Wk
Vk
A
15
12
B
10
8
C
12
9
D
8
5
2 D配列の宣言
m[i][j]は、i番目のアイテムに直面し、リュックサック容量がjの場合に得られる最大の価値を表す
j < w[i]
この場合、リュックサックの容量が不足してi番目のものを置くには、m[ i ][ j ] = m[ i-1 ][ j ]を取らないしかありません.
j>=w[i]
このときリュックサックの容量はi番目のものを置くことができて、私たちはこのものを持ってもっと大きな価値を得ることができるかどうかを考えなければなりません.
取ったらm[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]ここでのm[i-1][j-w[i]]とは、i-1アイテムを考慮したリュックサック容量がj-w[i]のときの最大の価値であり、i番目のアイテムのためにw[i]を空けたスペースに相当する.
持たなければm[ i ][ j ] = m[ i-1 ][ j ]

	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= c; j++){
			if (j >= w[i])
				m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);
			else
				m[i][j] = m[i - 1][j];
		}
	}

完全なコード

#include 
#include 
#include 

using namespace std;

int main()
{
	int v[7] = { 0,8,10,6,3,7,2 };
	int w[7] = { 0,4,6,2,2,5,1 };

	int m[100][100];
	int n = 6, c = 12;
	memset(m, 0, sizeof(m));
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= c; j++){
			if (j >= w[i])
				m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);
			else
				m[i][j] = m[i - 1][j];
		}
	}

	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= c; j++)
			cout << m[i][j] << ' ';
		cout << endl;
	}
		
	return 0;
}