### 第38题

**完善程序（二）0-1 背包问题 - 动态规划**（下列程序供第 38~42 题使用）

有 $n$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积是 $w_i$，价值是 $v_i$。每件物品最多只能使用一次。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。试补全空间优化后的动态规划程序。

```cpp
01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04 using namespace std;
05
06 int main() {
07 int n, V;
08 cin >> n >> V;
09 vector<int> w(n + 1), v(n + 1);
10 for (int i = 1; i <= n; i++) {
11 cin >> w[i] >> v[i];
12 }
13
14 vector<int> dp(①, 0);
15
16 for (int i = 1; i <= n; i++) {
17 for (int j = ②; j >= ③; j--) {
18 dp[j] = max(dp[j], ④);
19 }
20 }
21
22 cout << ⑤ << endl;
23 return 0;
24 }
```

**单选题**：① 处应填（　）。