#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, W;
    cout << "Masukkan jumlah item: ";
    cin >> n;
    cout << "Masukkan kapasitas tas: ";
    cin >> W;
 
    vector<int> nilai(n), berat(n);
    cout << "Masukkan nilai dan berat tiap item (nilai berat):\n";
    for (int i = 0; i < n; i++) cin >> nilai[i] >> berat[i];
 
    vector<int> dp(W + 1, 0);
 
    // Proses knapsack dengan DP (1D)
    for (int i = 0; i < n; i++)
        for (int j = W; j >= berat[i]; j--)
            dp[j] = max(dp[j], dp[j - berat[i]] + nilai[i]);
 
    cout << "\nNilai maksimum yang dapat dibawa = " << dp[W] << endl;
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKICAgIGludCBuLCBXOwogICAgY291dCA8PCAiTWFzdWtrYW4ganVtbGFoIGl0ZW06ICI7CiAgICBjaW4gPj4gbjsKICAgIGNvdXQgPDwgIk1hc3Vra2FuIGthcGFzaXRhcyB0YXM6ICI7CiAgICBjaW4gPj4gVzsKCiAgICB2ZWN0b3I8aW50PiBuaWxhaShuKSwgYmVyYXQobik7CiAgICBjb3V0IDw8ICJNYXN1a2thbiBuaWxhaSBkYW4gYmVyYXQgdGlhcCBpdGVtIChuaWxhaSBiZXJhdCk6XG4iOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIGNpbiA+PiBuaWxhaVtpXSA+PiBiZXJhdFtpXTsKCiAgICB2ZWN0b3I8aW50PiBkcChXICsgMSwgMCk7CgogICAgLy8gUHJvc2VzIGtuYXBzYWNrIGRlbmdhbiBEUCAoMUQpCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICBmb3IgKGludCBqID0gVzsgaiA+PSBiZXJhdFtpXTsgai0tKQogICAgICAgICAgICBkcFtqXSA9IG1heChkcFtqXSwgZHBbaiAtIGJlcmF0W2ldXSArIG5pbGFpW2ldKTsKCiAgICBjb3V0IDw8ICJcbk5pbGFpIG1ha3NpbXVtIHlhbmcgZGFwYXQgZGliYXdhID0gIiA8PCBkcFtXXSA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0K

NQo1IDQgNyA4IDEwCjEwIDUgNyAxMiA4CjIw

5
5 4 7 8 10
10 5 7 12 8
20