# What if the knapsack is very large (e.g., 100000000000000)?

這題的想法可以從找最大的 value 變成找最少的 weight，
所以表格裡面可以先預設為最大值。

轉移式為：$dp[1][j + value[i]] = min(dp[0][j + value[i]], dp[0][j] + value[i])$

最後我們只需要在最後的row從後面往前面走，第一個 weight 小於等於 max weight 的就是我們的最大 value。

:::info
這題只需要看上一次的結果所以可以一直 swap vector 來減少空間使用。
C++裡面直接做是 $O(1)$
:::

// 裡面的item[i]是value[i]的意思
vector<ll> dp[2];
for(int i = 0; i < 100001; i++){
    dp[0].push_back(INF64);
    dp[1].push_back(INF64);
}

for(int i = 0; i < n; i++){
    for(int j = 0; j < dp[0].size(); j++){
        if(dp[0][j] != INF64){
            dp[1][j] = min(dp[1][j], dp[0][j]);
            dp[1][j + item[i]] = min(dp[0][j + item[i]], dp[0][j] + weight[i]);
        }
    }
    dp[1][item[i]] = min(weight[i], dp[1][item[i]]);
    swap(dp[0], dp[1]);
}

for(int i = dp[0].size() - 1; i >= 0; i--){
    if(dp[0][i] <= w){
        cout << i;
        return 0;
    }
}