#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    // 1. Data Input Sesuai Kasus Anda
    const int N = 5;                        // Jumlah item
    const vector<int> W = {5, 4, 7, 8, 10}; // Bobot
    const vector<int> V = {10, 5, 7, 12, 8}; // Nilai
    const int C = 20;                       // Kapasitas
 
    // 2. Inisialisasi Tabel DP
    // dp[w] = Nilai max untuk kapasitas 'w'
    vector<int> dp(C + 1, 0); 
 
    // 3. Algoritma Dynamic Programming
    for (int i = 0; i < N; i++) {
        int current_weight = W[i];
        int current_value = V[i];
 
        // Iterasi kapasitas dari C ke current_weight (PENTING untuk 0/1 Knapsack)
        for (int w = C; w >= current_weight; w--) {
            // dp[w] = max(TIDAK diambil, diambil)
            dp[w] = max(dp[w], current_value + dp[w - current_weight]);
        }
    }
 
    // 4. Output Hasil
    // Nilai maksimal berada di dp[C]
    cout << "Nilai Maksimal: " << dp[C] << endl;
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewogICAgLy8gMS4gRGF0YSBJbnB1dCBTZXN1YWkgS2FzdXMgQW5kYQogICAgY29uc3QgaW50IE4gPSA1OyAgICAgICAgICAgICAgICAgICAgICAgIC8vIEp1bWxhaCBpdGVtCiAgICBjb25zdCB2ZWN0b3I8aW50PiBXID0gezUsIDQsIDcsIDgsIDEwfTsgLy8gQm9ib3QKICAgIGNvbnN0IHZlY3RvcjxpbnQ+IFYgPSB7MTAsIDUsIDcsIDEyLCA4fTsgLy8gTmlsYWkKICAgIGNvbnN0IGludCBDID0gMjA7ICAgICAgICAgICAgICAgICAgICAgICAvLyBLYXBhc2l0YXMKCiAgICAvLyAyLiBJbmlzaWFsaXNhc2kgVGFiZWwgRFAKICAgIC8vIGRwW3ddID0gTmlsYWkgbWF4IHVudHVrIGthcGFzaXRhcyAndycKICAgIHZlY3RvcjxpbnQ+IGRwKEMgKyAxLCAwKTsgCgogICAgLy8gMy4gQWxnb3JpdG1hIER5bmFtaWMgUHJvZ3JhbW1pbmcKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CiAgICAgICAgaW50IGN1cnJlbnRfd2VpZ2h0ID0gV1tpXTsKICAgICAgICBpbnQgY3VycmVudF92YWx1ZSA9IFZbaV07CiAgICAgICAgCiAgICAgICAgLy8gSXRlcmFzaSBrYXBhc2l0YXMgZGFyaSBDIGtlIGN1cnJlbnRfd2VpZ2h0IChQRU5USU5HIHVudHVrIDAvMSBLbmFwc2FjaykKICAgICAgICBmb3IgKGludCB3ID0gQzsgdyA+PSBjdXJyZW50X3dlaWdodDsgdy0tKSB7CiAgICAgICAgICAgIC8vIGRwW3ddID0gbWF4KFRJREFLIGRpYW1iaWwsIGRpYW1iaWwpCiAgICAgICAgICAgIGRwW3ddID0gbWF4KGRwW3ddLCBjdXJyZW50X3ZhbHVlICsgZHBbdyAtIGN1cnJlbnRfd2VpZ2h0XSk7CiAgICAgICAgfQogICAgfQoKICAgIC8vIDQuIE91dHB1dCBIYXNpbAogICAgLy8gTmlsYWkgbWFrc2ltYWwgYmVyYWRhIGRpIGRwW0NdCiAgICBjb3V0IDw8ICJOaWxhaSBNYWtzaW1hbDogIiA8PCBkcFtDXSA8PCBlbmRsOwoKICAgIHJldHVybiAwOwp9

OAozIDEwIDYgNyA5IDEwIDcgNQoxIDEwIDggMSA3IDggOSAxOAozNQ==

8
3 10 6 7 9 10 7 5
1 10 8 1 7 8 9 18
35