読者です 読者をやめる 読者になる 読者になる

初めての投稿

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
*/

<||