初めての投稿
test
ナップサック問題を解いた
深さ優先探索を用いたものと、漸化式を利用した2重ループを用いた解法の2つ
#include <iostream> #include <map> #include <queue> #include <algorithm> #include <cstring> using namespace std; typedef pair<int,int> P; int dfs(vector <P> vec, int i, int w, int v, int W){ if(i==vec.size() || w>=W) return 0; return max( dfs(vec,i+1,w+vec[i].first, v+vec[i].second,W)+v,dfs(vec,i+1,w, v,W)); } int main(void){ int n; cin >> n; vector <P> v(n); for(int i=0; i<n; i++){ int a,b; cin >> a >> b; v[i] = P(a,b); } int w; cin >> w; // sort(v.begin(), v.end()); cout << dfs(v,0,0,0,w) << endl; // without dfs only loop // int** dp = new int*[n+1]; // for(int i=0; i<n+1; i++){ // dp[i] = new int[w+1]; // } int dp[5][6]; memset(dp,0,sizeof(dp)); for(int i=0; i<n+1; i++){ for(int j=0; j<w+1; j++){ cout << dp[i][j] << " "; } cout << endl; } for(int i=n-1; i>=0; i--){ for(int j=1; j<w+1;j++){ if(j<v[i].first){ dp[i][j]=dp[i+1][j]; }else{ dp[i][j] = max(dp[i+1][j], dp[i+1][j-v[i].first]+v[i].second); } } } cout << dp[0][5] << endl; for(int i=0; i<n+1; i++){ for(int j=0; j<w+1; j++){ cout << dp[i][j] << " "; } cout << endl; } return 0; } /* sample input 4 2 3 1 2 3 4 2 2 5 ans 7 */ <||