Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Knapsack Problem"
https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_C
・ナップザック問題
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #DPL_1_C : Knapsack Problem
/* Aizu Online Judge in C++ #DPL_1_C : Knapsack Problem https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_C 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int N,W; cin>>N>>W; int dp[100000]; fill_n(dp,W+1,-1); dp[0]=0; for(int i=0;i<N;i++){ int v,w; cin>>v>>w; for(int j=w;j<=W;j++){ if(dp[j-w]!=-1){ dp[j]=max(dp[j],dp[j-w]+v); } } } cout<<*max_element(dp,dp+W+1)<<endl; return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/