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