Đây là bài toán quy hoạch động cái túi cơ bản. Lưu ý rằng vì ~v_i \le 10^9~, ta không thể lưu ~v_i~ trong mảng ~dp~ của mình. Thay vào đó, có thể lưu khối lượng ~W~ ~(W \le 10^5)~. Gọi ~dp[i][j]~ là tổng giá trị lớn nhất có thể khi xét ~i~ đồ vật đầu tiên và có tổng khối lượng là ~j~. Bài toán trở về quy hoạch động cái túi cơ bản.

Độ phức tạp thuật toán: ~O(N \cdot W)~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int mx = 1e5+1;

template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}

long long dp[101][mx];
int w[101], v[101];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N, W; cin >> N >> W;
    for(int i = 0; i < N; ++i) cin >> w[i] >> v[i];

    for(int i = 0; i < N; ++i) for(int j = 0; j <= W; ++j) {
        if(j + w[i] <= W) ckmax(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
        ckmax(dp[i + 1][j], dp[i][j]);
    }

    cout << dp[N][W] << endl;
}