📝 题目大意

本题是一道经典的混合型动态规划问题。可以看作是 “0/1背包问题” 与 “打家劫舍问题（不相邻子序列）” 的结合体。 题目要求我们在 $N$ 个物品中选择若干个，装入载重限制为 $W$ 的直升机中，使得总价值最大。与此同时，附加了一个额外限制：不能同时选择相邻的两个物品。

💡 解题思路

解决这道题的核心在于设计正确的状态表示。普通的背包问题只需要记录“处理到第几个物品”和“当前消耗的重量”，但由于本题存在“不能取相邻物品”的限制，我们还需要记录“上一个物品是否被选中”。

1. 状态定义

设 dp[i][j][0] 表示考虑到第 $i$ 个物品，当前总重量为 $j$，且 不选择 第 $i$ 个物品时能获得的最大价值。 设 dp[i][j][1] 表示考虑到第 $i$ 个物品，当前总重量为 $j$，且 选择 第 $i$ 个物品时能获得的最大价值。

2. 状态转移方程

对于第 $i$ 个物品，我们有两种决策：

• 不选择第 $i$ 个物品： 那么第 $i-1$ 个物品既可以选，也可以不选，我们只需取两者的最大值。

  $$dp[i][j][0] = \max(dp[i-1][j][0], dp[i-1][j][1])$$

• 选择第 $i$ 个物品： 要想选择第 $i$ 个物品，必须满足当前总重量 $j \ge w[i]$。并且，因为不能选择相邻的物品，所以第 $i-1$ 个物品绝对不能被选中。

  $$dp[i][j][1] = dp[i-1][j-w[i]][0] + v[i]$$

3. 空间优化（滚动数组）

由于第 $i$ 层的状态仅仅依赖于第 $i-1$ 层的状态，我们可以省掉第一维 $i$ 的空间开销。维护一个二维数组 dp[j][0/1]，在遍历每个物品时，使用一个新数组 next_dp[j][0/1] 计算当前层的状态，然后滚动覆盖即可。这就将空间复杂度降到了 $O(W)$。

⏱️ 复杂度分析

• 时间复杂度： $O(N \cdot W)$。其中 $N$ 是物品数量，$W$ 是直升机最大载重。外层循环遍历 $N$ 个物品，内层循环遍历 $W$ 种重量状态。极限数据下计算量约为 $1000 \times 10000 = 10^7$ 次操作，在 C++ 中只需十几毫秒即可跑完。
• 空间复杂度： $O(W)$。利用滚动数组优化掉了物品维度的空间，实际只需要两个大小为 $(W+1) \times 2$ 的整型数组，内存占用小于 1 MB，非常优秀。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 关闭输入输出同步，提升读取速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, W;
    if (!(cin >> N >> W)) return 0;

    vector<int> v(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i];
    }

    vector<int> w(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> w[i];
    }

    // 状态数组定义：
    // dp[j][0]：总重量限制为 j 时，且【不选】上一物资的最大价值
    // dp[j][1]：总重量限制为 j 时，且【选择】上一物资的最大价值
    // 初始化为 0
    vector<vector<int>> dp(W + 1, vector<int>(2, 0));

    for (int i = 1; i <= N; ++i) {
        // 用于保存处理第 i 个物品后的新状态
        vector<vector<int>> next_dp(W + 1, vector<int>(2, 0));
        
        for (int j = 0; j <= W; ++j) {
            // 决策 1：不选当前物品 i
            // 那么物品 i-1 可以选也可以不选，取两者最大值
            next_dp[j][0] = max(dp[j][0], dp[j][1]);
            
            // 决策 2：选择当前物品 i
            // 前提条件：背包容量足够装下物品 i
            if (j >= w[i]) {
                // 如果选了物品 i，那么物品 i-1 必然不能被选（即状态只能从 dp[...][0] 转移过来）
                next_dp[j][1] = dp[j - w[i]][0] + v[i];
            }
        }
        // 滚动数组更新，将新状态赋给旧状态，为下一个物品做准备
        dp = next_dp;
    }

    // 在最终所有的合法状态中寻找能获取的最大价值
    int max_value = 0;
    for (int j = 0; j <= W; ++j) {
        max_value = max({max_value, dp[j][0], dp[j][1]});
    }

    cout << max_value << "\n";
    
    return 0;
}