程序一：最大不相邻元素和

数组按 1 下标保存。完成第 1～6 题。

int a[6] = {0, 3, 2, 7, 10, 12};
int dp[6];
dp[0] = 0;
dp[1] = a[1];
for (int i = 2; i <= 5; ++i)
    dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
cout << dp[5];

第 1 题

dp[i] 的含义是（ ）。

{{ select(1) }}

• 前 i 个数中选择互不相邻元素能得到的最大和
• 前 i 个数的总和
• 第 i 个数的值
• 长度为 i 的最短路

---

第 2 题

dp[2] 的值是多少？

{{ input(2) }}

---

第 3 题

dp[3] 的值是多少？

{{ input(3) }}

---

第 4 题

dp[4] 的值是多少？

{{ input(4) }}

---

第 5 题

程序最终输出多少？

{{ input(5) }}

---

第 6 题

该程序的时间复杂度和数组空间复杂度都是（ ）。

{{ select(6) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n^2)$

---

程序二：一维 0/1 背包

容量为 6，三件物品的 (重量,价值) 为 (2,4),(3,5),(4,7)。完成第 7～12 题。

int W = 6;
int w[4] = {0,2,3,4};
int val[4] = {0,4,5,7};
int dp[7] = {};
for (int i = 1; i <= 3; ++i)
    for (int j = W; j >= w[i]; --j)
        dp[j] = max(dp[j], dp[j - w[i]] + val[i]);

第 7 题

处理完前两件物品后，dp[5] 的值是多少？

{{ input(7) }}

---

第 8 题

处理完全部物品后，dp[6] 的值是多少？

{{ input(8) }}

---

第 9 题

得到最优值 11 时选择的是（ ）。

{{ select(9) }}

• 第1件和第2件
• 第1件和第3件
• 第2件和第3件
• 三件全部

---

第 10 题

容量循环倒序的原因是（ ）。

{{ select(10) }}

• 保证同一件物品本轮最多使用一次
• 让数组自动有序
• 避免访问 dp[0]
• 降低到 $O(1)$ 时间

---

第 11 题

若错误地把容量循环改为从小到大，处理第一件物品后 dp[6] 可能变成多少？

{{ input(11) }}

---

第 12 题

该程序时间复杂度是（ ）。

{{ select(12) }}

• $O(n+W)$
• $O(nW)$
• $O(\log W)$
• $O(2^W)$

---