Submission #5814251
Source Code Expand
#include<bits/stdc++.h> #define REP(i,n) for(int i = 0; i < n; i++) #define RREP(i,n) for(int i = n-1; i >= 0; i--) using namespace std; typedef long long ll; static const ll INF = 1 << 30; static const int MAX_N = 200; static const int MAX_V = 1000; ll N, W; vector<ll> Value, Weight; pair<ll, ll> ps[1 << (30/2)]; //重さ、価値 /* ll rec(int point, ll v, ll w){ if(point >= N){ return v; }else{ if(w + Weight[point] > W) return rec(point+1,v,w); else{ return max(rec(point+1, v, w), rec(point+1,v + Value[point], w + Weight[point])); } } return 0; }*/ map<ll,ll> ls[2]; void brute(int i,int end,ll wsum,ll vsum,int op){ if(i==end){ if(wsum<=W) ls[op][wsum]=max(ls[op][wsum],vsum); return; } brute(i+1,end,wsum+w[i],vsum+v[i],op); brute(i+1,end,wsum,vsum,op); } void solve(){ //前半全列挙 int n2 = N / 2; for(int i = 0; i < 1 << n2; i++){ ll sw = 0, sv = 0; for(int j = 0; j < n2; j++){ if(i >> j & 1){ sw += Weight[j]; sv += Value[j]; } } ps[i] = make_pair(sw,sv); } //ムダな要素を省く sort(ps, ps + (1 << n2)); int m = 1; for(int i = 1; i < 1 << n2; i++){ if(ps[m-1].second < ps[i].second){ ps[m++] = ps[i]; } } //cout << m << endl; //後ろ半分を全列挙し解を求める ll res = 0; for(int i = 0; i < 1 << (N - n2); i++){ ll sw = 0, sv = 0; for(int j = 0; j < N - n2; j++){ if(i >> j & 1){ sw += Weight[n2 + j]; sv += Value[n2 + j]; } } if(sw <= W){ ll tv = (lower_bound(ps, ps + m, make_pair(W - sw, INF)) - 1)->second; res = max(res, sv + tv); } } printf("%lld\n", res); } int main(){ cin >> N >> W; REP(i,N){ int v, w; cin >> v >> w; Value.push_back(v); Weight.push_back(w); } if(N <= 30){ //cout << rec(0,0,0) << endl;//これだとWがデカイ時にあかん。 //solve(); brute(0,N/2,0,0,0); brute(N/2,N,0,0,1); ll ans=0; deque<pair<ll,ll>> dq; vector<pair<ll,ll>> vec; for(auto it:ls[1]) vec.push_back(it); reverse(vec.begin(),vec.end());//重い順に並び替え //重い順にdequeに突っ込んでいって価値順に並べる for(auto it:vec){ while(!dq.empty()&&dq.back().second<it.second){ dq.pop_back(); } dq.push_back(it); } for(auto i:ls[0]){//ls[0]は軽い順に見る ll curw=i.first,curv=i.second; while(!dq.empty()&&curw+dq.front().first>W) dq.pop_front(); ans=max(ans,curv+dq.front().second); } cout<<ans<<endl; return 0; }else{ bool flag = 1; REP(i,N){ if(Weight[i] > 1000 || Weight[i] < 0) flag = 0; } if(flag){//weight1000以下 ll dpw[1001] = {0};//重さw以下で最大の価値 REP(i,N){ RREP(j, W+1){ if(j-Weight[i] >= 0) dpw[j] = max(dpw[j], dpw[j-Weight[i]] + Value[i]); } } cout << dpw[W] << endl; }else{//value 1000以下 ll dp[2][MAX_N * MAX_V + 1];//dp[i+1][j]:=i番目までの品物から価値の総和がjとなるように選んだ時の重さの総和の最小値 dp[0][0] = 0; for(int i = 1; i < MAX_N * MAX_V; i++){ dp[0][i] = INF; } for(int i = 1; i <= N; i++){ for(int j = 0; j <= MAX_N * MAX_V; j++){ bool s = i % 2; bool t = !s; if(j - Value[i-1] >= 0){ dp[s][j] = min(dp[t][j], dp[t][j-Value[i-1]]+ Weight[i-1]); //cout << "yes\n"; } else { dp[s][j] = dp[t][j]; //cout << "no\n"; } } } int res = 0; REP(i, MAX_N * MAX_V){ //cout << dp[N%2][i] << endl; if(dp[N%2][i] <= W) { res = i; //cout << res << endl; } } cout << res << endl; //cout << INF << endl; } } }
Submission Info
Submission Time | |
---|---|
Task | D - ナップサック問題 |
User | raoZ |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 4715 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘void brute(int, int, ll, ll, int)’: ./Main.cpp:33:24: error: ‘w’ was not declared in this scope brute(i+1,end,wsum+w[i],vsum+v[i],op); ^ ./Main.cpp:33:34: error: ‘v’ was not declared in this scope brute(i+1,end,wsum+w[i],vsum+v[i],op); ^