AtCoder Beginner Contest 032 D - ナップサック問題
「ナップサック問題か〜どのナップサックかな〜 多分半分全列挙?」「全部です」「はい」
解法
蟻本に載ってるナップサック問題の解法を試せば良いです。蟻本第二版での話ですが,
半分全列挙 -> p148
w[i] <= 1000 (一番シンプルなやつ) -> p52
v[i] <= 1000 -> p60
に書いてあります。
ll v[222], w[222]; pll ps[1<<16]; ll dp[2][222*1000]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; ll W; cin >> N >> W; for (int i = 0; i < N; i++) cin >> v[i] >> w[i]; if (N <= 30) { int n = N/2; for (int i = 0; i < 1<<n; i++) { ll sw = 0, sv = 0; for (int j = 0; j < n; j++) { if ((i>>j)&1) { sw += w[j]; sv += v[j]; } } ps[i] = pll(sw, sv); } sort(ps, ps+(1<<n)); int m = 1; for (int i = 1; i < 1<<n; i++) { if (ps[m-1].second < ps[i].second) ps[m++] = ps[i]; } ll res = 0; for (int i = 0; i < 1<<(N-n); i++) { ll sw = 0, sv = 0; for (int j = 0; j < N-n; j++) { if ((i>>j)&1) { sw += w[n+j]; sv += v[n+j]; } } if (sw <= W) { ll tv = (lower_bound(ps, ps+m, make_pair(W-sw, 1ll<<55))-1)->second; res = max(res, sv+tv); } } cout << res << endl; return 0; } bool flag = true; for (int i = 0; i < N; i++) flag &= w[i] <= 1000; memset(dp, -1, sizeof(dp)); dp[0][0] = 0; if (flag) { for (int i = 0; i < N; i++) { int cur = i%2, tar = cur^1; for (int j = 0; j <= i*1010; j++) dp[tar][j] = -1; for (int j = 0; j <= i*1010; j++) { if (dp[cur][j] == -1) continue; dp[tar][j] = max(dp[tar][j], dp[cur][j]); dp[tar][j+w[i]] = max(dp[tar][j+w[i]], dp[cur][j]+v[i]); } } ll ans = 0; for (int i = 0; i < 222*1000 && i <= W; i++) { ans = max(ans, dp[N%2][i]); } cout << ans << endl; } else { for (int i = 0; i < N; i++) { int cur = i%2, tar = cur^1; for (int j = 0; j <= i*1010; j++) dp[tar][j] = -1; for (int j = 0; j <= i*1010; j++) { if (dp[cur][j] == -1) continue; if (dp[tar][j] == -1 || dp[tar][j] > dp[cur][j]) dp[tar][j] = dp[cur][j]; if (dp[tar][j+v[i]] == -1 || dp[tar][j+v[i]] > dp[cur][j] + w[i]) dp[tar][j+v[i]] = dp[cur][j]+w[i]; } } ll ans = 0; for (int i = 0; i < 222*1000; i++) { if (dp[N%2][i] != -1 && dp[N%2][i] <= W) ans = i; } cout << ans << endl; } return 0; }