ナップサック問題を動的計画法で

解くコードを書いてみた。
漸化式を思いつけるようになりたい。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 100; //品物の最大個数
const int MAX_W = 10000; //最大の重さ
int N, W; //品物の個数、ナップサックに入る重さ

typedef pair<int ,int> T; //重さ、価値
T thing[MAX_N]; //品物の情報

int dp[MAX_N + 1][MAX_W + 1]; //DPテーブル
/*
dp[i][j] := i番目までの品物を重さj以下となるように選んだときの価値の最大

dp[0][j] = 0

           { dp[i - 1][j]		(thing[i].first > j)
dp[i][j] = {
           { max(dp[i - 1][j], dp[i - 1][j - thing[i].first] + thing[i].second)
*/
int solve(){
	for(int i = 1; i <= N; i++){
		for(int j = 0; j <= W; j++){
			if(thing[i].first > j)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - thing[i].first] + thing[i].second);
		}
	}

	return dp[N][W];
}
int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		scanf("%d %d", &thing[i + 1].first, &thing[i + 1].second);
	}
	scanf("%d", &W);
	printf("%d\n", solve());
	return 0;
}