只留两行也能算对

下面只开两行，用 i & 1 轮流当「这一行」和「上一行」。运行这段程序：

本路线的物品：(重 3 值 8)、(重 4 值 9)、(重 5 值 11)，写成 vector<pair<int, int>>，auto [w, v] 取出重量和价值。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Item = pair<int, int>;   // (重量, 价值)

const vector<Item> ITEMS = {{3, 8}, {4, 9}, {5, 11}};

long long knap_roll(const vector<Item>& items, int cap) {
    int n = items.size();
    vector<vector<long long>> dp(2, vector<long long>(cap + 1, 0));
    for (int i = 1; i <= n; i++) {
        auto [w, v] = items[i - 1];
        int cur = i & 1, pre = cur ^ 1;
        for (int c = 0; c <= cap; c++) {
            dp[cur][c] = dp[pre][c];
            if (c >= w && dp[pre][c - w] + v > dp[cur][c]) dp[cur][c] = dp[pre][c - w] + v;
        }
    }
    return dp[n & 1][cap];
}

int main() {
    cout << knap_roll(ITEMS, 10) << "/" << 2 << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）