[AtCoder] Educational DP Contest E – Knapsack 2
問題
方針
商品の重さの最大値が \( 10^9\) なので、添え字で重さを管理して考えるのはメモリ的にきついので、別の方法を考えます。価値を添え字で管理することを考えます。\( d(i, j)\) を商品 \( i \) まで調べたとき、価値の総和が \( j \) であるときのナップザックの重さとします。初期値は、\( d(0, 0) = 0\) でそれ以外は、\( d(i, j) = \infty \) とします。 また、価値の総和の最大値は \( 10^5 \) であることに注意します。この配列の更新式は、
- \(d(i, j) \neq \infty\) のとき
\[
\begin{eqnarray}
d(i + 1, j) &=& \min(d(i, j) , d(i + 1, j))\\
d(i + 1, j + v_i) &=& min(d(i + 1, j + v_i), d(i, j) + w_i)
\end{eqnarray}
\]
となります。答えは、\(d[N][i] \leq W \) を満たす最大の \( i \) となります。また、\( d(i, j) + w_i > W\) となる商品 \( i \) は考慮しなくてよいので、更新時に省きます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int d[101][100001]; int main() { int N, W; cin >> N >> W; int w[N], v[N]; for (int i = 0; i < N; i++) { cin >> w[i] >> v[i]; } int l = 100001; for (int i = 0; i <= N; i++) { for (int j = 0; j < l; j++) { d[i][j] = INT32_MAX; } } d[0][0] = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < l; j++) { if (d[i][j] == INT32_MAX) continue; d[i + 1][j] = min(d[i + 1][j], d[i][j]); if (d[i][j] + w[i] > W) continue; d[i + 1][j + v[i]] = min(d[i + 1][j + v[i]], d[i][j] + w[i]); } } int ans = 0; for (int i = 0; i < l; i++) { if (d[N][i] <= W) { ans = i; } } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません