アルゴ式(beta版)の「動的計画法」部分和問題とナップサック問題からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。
Q3-1. 部分和問題 (導入編)
/* C++による「動的計画法」部分和問題とナップサック問題の解答例 Q3-1. 部分和問題 (導入編) https://algo-method.com/tasks/336 提出コードの解答例 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-1); for(int i=0;i<n-1;i++){ cin>>a[i]; } vector<vector<bool>> dp(n,vector<bool>(m,false)); dp[0][0]=true; for(int i=0;i<n-1;i++){ for(int j=0;j<m;j++){ if(dp[i][j]==false){ continue; } dp[i+1][j]=true; if(j+a[i]<m){ dp[i+1][j+a[i]]=true; } } } int ans=0; for(int i=0;i<m;i++){ if(dp[n-1][i]){ ans++; } } cout<<ans<<endl; return 0; }
・Q3-2. 部分和問題
/* C++による「動的計画法」部分和問題とナップサック問題の解答例 Q3-2. 部分和問題 https://algo-method.com/tasks/337 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m; cin>>n>>m; vector<int> w(n); for(int i=0;i<n;i++){ cin>>w[i]; } vector<vector<bool>> dp(n+1,vector<bool>(m,false)); dp[0][0]=true; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){ if(dp[i][j]==false){ continue; } dp[i+1][j]=true; if(j+w[i]<=m){ dp[i+1][j+w[i]]=true; } } } if(dp[n][m]){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } return 0; }
・Q3-3. ナップサック問題 (導入編)
/* C++による「動的計画法」部分和問題とナップサック問題の解答例 Q3-3. ナップサック問題 (導入編) https://algo-method.com/tasks/341 提出コードの解答例 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-1),b(n-1); for(int i=0;i<n-1;i++){ cin>>a[i]; } for(int i=0;i<n-1;i++){ cin>>b[i]; } vector<vector<int>> dp(n,vector<int>(m,-1)); dp[0][0]=0; for(int i=0;i<n-1;i++){ for(int j=0;j<m;j++){ if(dp[i][j]<0){ continue; } dp[i+1][j]=max(dp[i+1][j],dp[i][j]); if(j+a[i]<m){ dp[i+1][j+a[i]]=max(dp[i+1][j+a[i]],dp[i][j]+b[i]); } } } cout<<dp[n-1][m-1]<<endl; return 0; }
・Q3-4. ナップサック問題
/* C++による「動的計画法」部分和問題とナップサック問題の解答例 Q3-4. ナップサック問題 https://algo-method.com/tasks/329 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m; cin>>n>>m; vector<int> w(n),v(n); for(int i=0;i<n;i++){ cin>>w[i]; } for(int i=0;i<n;i++){ cin>>v[i]; } vector<vector<int>> dp(n+1,vector<int>(m+1,-1)); dp[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){ if(dp[i][j]<0){ continue; } dp[i+1][j]=max(dp[i+1][j],dp[i][j]); if(j+w[i]<=m){ dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]); } } } int ans=-1; for(int i=0;i<=m;i++){ ans=max(ans,dp[n][i]); } cout<<ans<<endl; return 0; }
・Q3-5. 部分和問題 (応用 1)
/* C++による「動的計画法」部分和問題とナップサック問題の解答例 Q3-5. 部分和問題 (応用 1) https://algo-method.com/tasks/350 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; #define INF 100000000 int main(void){ int n,m; cin>>n>>m; vector<int> w(n); for(int i=0;i<n;i++){ cin>>w[i]; } vector<vector<int>> dp(n+1,vector<int>(m+1,INF)); dp[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){ if(dp[i][j]==INF){ continue; } dp[i+1][j]=min(dp[i+1][j],dp[i][j]); if(j+w[i]<=m){ dp[i+1][j+w[i]]=min(dp[i+1][j+w[i]],dp[i][j]+1); } } } if(dp[n][m]==INF){ cout<<-1<<endl; }else{ cout<<dp[n][m]<<endl; } return 0; }
・Q3-6. 部分和問題 (応用 2)
/* C++による「動的計画法」部分和問題とナップサック問題の解答例 Q3-6. 部分和問題 (応用 2) https://algo-method.com/tasks/352 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,a,b; cin>>n>>a>>b; vector<int> x(n); for(int i=0;i<n;i++){ cin>>x[i]; } vector<vector<bool>> dp(n+1,vector<bool>(a,false)); dp[0][0]=true; for(int i=0;i<n;i++){ for(int j=0;j<a;j++){ if(dp[i][j]==false){ continue; } dp[i+1][j]=true; dp[i+1][(j+x[i])%a]=true; } } if(dp[n][b]){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } return 0; }
・Q3-7. ボールと 2 つの箱
/* C++による「動的計画法」部分和問題とナップサック問題の解答例 Q3-7. ボールと 2 つの箱 https://algo-method.com/tasks/335 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<int> w(n); for(int i=0;i<n;i++){ cin>>w[i]; } int m=0; for(int i=0;i<n;i++){ m+=w[i]; } vector<vector<bool>> dp(n+1,vector<bool>(m+1,false)); dp[0][0]=true; for(int i=0;i<n;i++){ for(int j=0;j<m+1;j++){ if(dp[i][j]==false){ continue; } dp[i+1][j+w[i]]=true; dp[i+1][abs(j-w[i])]=true; } } int ans=0; while(dp[n][ans]==false){ ans++; } cout<<ans<<endl; return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com