アルゴ式（beta版）の「【特集】典型的な動的計画法のパターンを整理 ～ ナップサック DP 編 ～」部分和問題とその応用たちからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
問題 3：部分和問題
/* C++による「【特集】典型的な動的計画法のパターンを整理 ～ ナップサック DP 編 ～」部分和問題とその応用たちの解答例 問題 3：部分和問題 https://algo-method.com/tasks/309 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m; cin>>n>>m; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } bool dp[n+1][m+1]; memset(dp,false,sizeof(dp)); dp[0][0]=true; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){ dp[i+1][j]|=dp[i][j]; if(j>=a[i]){ dp[i+1][j]|=dp[i][j-a[i]]; } } } if(dp[n][m]){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } return 0; }
・問題 4：部分和数え上げ問題
/* C++による「【特集】典型的な動的計画法のパターンを整理 ～ ナップサック DP 編 ～」部分和問題とその応用たちの解答例 問題 4：部分和数え上げ問題 https://algo-method.com/tasks/310 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; const int mod=1000; int main(void){ int n,m; cin>>n>>m; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } vector<vector<int>> dp(n+1,vector<int>(m+1,0)); dp[0][0]=1; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){ dp[i+1][j]+=dp[i][j]; dp[i+1][j]%=mod; if(j>=a[i]){ dp[i+1][j]+=dp[i][j-a[i]]; dp[i+1][j]%=mod; } } } cout<<dp[n][m]<<endl; return 0; }
・問題 5：最小個数部分和問題
/* C++による「【特集】典型的な動的計画法のパターンを整理 ～ ナップサック DP 編 ～」部分和問題とその応用たちの解答例 問題 5：最小個数部分和問題 https://algo-method.com/tasks/311 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; const int big=100000000; int main(void){ int n,m; cin>>n>>m; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } vector<vector<int>> dp(n+1,vector<int>(m+1,big)); dp[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){ dp[i+1][j]=min(dp[i+1][j],dp[i][j]); if(j>=a[i]){ dp[i+1][j]=min(dp[i+1][j],dp[i][j-a[i]]+1); } } } if(dp[n][m]==big){ cout<<-1<<endl; }else{ cout<<dp[n][m]<<endl; } return 0; }
・問題 6：K 個以内部分和問題
/* C++による「【特集】典型的な動的計画法のパターンを整理 ～ ナップサック DP 編 ～」部分和問題とその応用たちの解答例 問題 6：K 個以内部分和問題 https://algo-method.com/tasks/312 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; const int big=100000000; int main(void){ int n,m,k; cin>>n>>m>>k; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } vector<vector<int>> dp(n+1,vector<int>(m+1,big)); dp[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){ dp[i+1][j]=min(dp[i+1][j],dp[i][j]); if(j>=a[i]){ dp[i+1][j]=min(dp[i+1][j],dp[i][j-a[i]]+1); } } } if(dp[n][m]<=k){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } return 0; }
・問題 7：個数制限付き部分和問題
/* C++による「【特集】典型的な動的計画法のパターンを整理 ～ ナップサック DP 編 ～」部分和問題とその応用たちの解答例 問題 7：個数制限付き部分和問題 https://algo-method.com/tasks/313 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; const int big=100000000; int main(void){ int n,m; cin>>n>>m; vector<int> a(n),b(n); for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; } vector<vector<int>> dp(n+1,vector<int>(m+1,big)); dp[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){ if(dp[i][j]<big){ dp[i+1][j]=0; } if(j>=a[i]){ if(dp[i][j-a[i]]<big){ dp[i+1][j]=min(dp[i+1][j],1); } if(dp[i+1][j-a[i]]<b[i]){ dp[i+1][j]=min(dp[i+1][j],dp[i+1][j-a[i]]+1); } } } } if(dp[n][m]==big){ cout<<"No"<<endl; }else{ cout<<"Yes"<<endl; } return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
