ナップサック問題を動的計画法で
解くコードを書いてみた。
漸化式を思いつけるようになりたい。
#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; }