#include <iostream>
#include <vector>
using namespace std;
 
// Fungsi untuk menghitung nilai maksimum dengan algoritma 0/1 Knapsack
int knapsack(int W, vector<int> w, vector<int> v, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (w[i - 1] <= j)
                dp[i][j] = max(v[i - 1] + dp[i - 1][j - w[i - 1]], dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
 
    return dp[n][W];
}
 
int main() {
    int n, W;
 
    cout << "Masukkan jumlah barang: ";
    cin >> n;
 
    vector<int> w(n), v(n);
 
    cout << "Masukkan bobot masing-masing barang: ";
    for (int i = 0; i < n; i++) cin >> w[i];
 
    cout << "Masukkan nilai masing-masing barang: ";
    for (int i = 0; i < n; i++) cin >> v[i];
 
    cout << "Masukkan kapasitas maksimal yang dapat ditampung: ";
    cin >> W;
 
    int hasil = knapsack(W, w, v, n);
 
    cout << "\nNilai maksimum yang dapat dibawa: " << hasil << endl;
 
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gRnVuZ3NpIHVudHVrIG1lbmdoaXR1bmcgbmlsYWkgbWFrc2ltdW0gZGVuZ2FuIGFsZ29yaXRtYSAwLzEgS25hcHNhY2sKaW50IGtuYXBzYWNrKGludCBXLCB2ZWN0b3I8aW50PiB3LCB2ZWN0b3I8aW50PiB2LCBpbnQgbikgewogICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBkcChuICsgMSwgdmVjdG9yPGludD4oVyArIDEsIDApKTsKCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICBmb3IgKGludCBqID0gMTsgaiA8PSBXOyBqKyspIHsKICAgICAgICAgICAgaWYgKHdbaSAtIDFdIDw9IGopCiAgICAgICAgICAgICAgICBkcFtpXVtqXSA9IG1heCh2W2kgLSAxXSArIGRwW2kgLSAxXVtqIC0gd1tpIC0gMV1dLCBkcFtpIC0gMV1bal0pOwogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICBkcFtpXVtqXSA9IGRwW2kgLSAxXVtqXTsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIGRwW25dW1ddOwp9CgppbnQgbWFpbigpIHsKICAgIGludCBuLCBXOwoKICAgIGNvdXQgPDwgIk1hc3Vra2FuIGp1bWxhaCBiYXJhbmc6ICI7CiAgICBjaW4gPj4gbjsKCiAgICB2ZWN0b3I8aW50PiB3KG4pLCB2KG4pOwoKICAgIGNvdXQgPDwgIk1hc3Vra2FuIGJvYm90IG1hc2luZy1tYXNpbmcgYmFyYW5nOiAiOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIGNpbiA+PiB3W2ldOwoKICAgIGNvdXQgPDwgIk1hc3Vra2FuIG5pbGFpIG1hc2luZy1tYXNpbmcgYmFyYW5nOiAiOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIGNpbiA+PiB2W2ldOwoKICAgIGNvdXQgPDwgIk1hc3Vra2FuIGthcGFzaXRhcyBtYWtzaW1hbCB5YW5nIGRhcGF0IGRpdGFtcHVuZzogIjsKICAgIGNpbiA+PiBXOwoKICAgIGludCBoYXNpbCA9IGtuYXBzYWNrKFcsIHcsIHYsIG4pOwoKICAgIGNvdXQgPDwgIlxuTmlsYWkgbWFrc2ltdW0geWFuZyBkYXBhdCBkaWJhd2E6ICIgPDwgaGFzaWwgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQo=

NgozIDggNSA0IDEwIDgKNiA0IDUgNiA1IDEw

6
3 8 5 4 10 8
6 4 5 6 5 10