#include <iostream>
#include <vector>
using namespace std;
 
int max(int a, int b) {
    return (a > b) ? a : b;
}
 
int knapSack(int W, vector<int> wt, vector<int> val, int n) {
    vector<vector<int>> K(n + 1, vector<int>(W + 1));
 
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
 
    return K[n][W];
}
 
int main() {
    int n = 5; // jumlah barang
    int W = 5; // kapasitas tas
 
    vector<int> val = {4, 8, 10, 7, 8};
    vector<int> wt  = {7, 10, 5, 12, 20};
 
    cout << "Nilai maksimum yang dapat dibawa = " << knapSack(W, wt, val, n) << endl;
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1heChpbnQgYSwgaW50IGIpIHsKICAgIHJldHVybiAoYSA+IGIpID8gYSA6IGI7Cn0KCmludCBrbmFwU2FjayhpbnQgVywgdmVjdG9yPGludD4gd3QsIHZlY3RvcjxpbnQ+IHZhbCwgaW50IG4pIHsKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gSyhuICsgMSwgdmVjdG9yPGludD4oVyArIDEpKTsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8PSBuOyBpKyspIHsKICAgICAgICBmb3IgKGludCB3ID0gMDsgdyA8PSBXOyB3KyspIHsKICAgICAgICAgICAgaWYgKGkgPT0gMCB8fCB3ID09IDApCiAgICAgICAgICAgICAgICBLW2ldW3ddID0gMDsKICAgICAgICAgICAgZWxzZSBpZiAod3RbaSAtIDFdIDw9IHcpCiAgICAgICAgICAgICAgICBLW2ldW3ddID0gbWF4KHZhbFtpIC0gMV0gKyBLW2kgLSAxXVt3IC0gd3RbaSAtIDFdXSwgS1tpIC0gMV1bd10pOwogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICBLW2ldW3ddID0gS1tpIC0gMV1bd107CiAgICAgICAgfQogICAgfQoKICAgIHJldHVybiBLW25dW1ddOwp9CgppbnQgbWFpbigpIHsKICAgIGludCBuID0gNTsgLy8ganVtbGFoIGJhcmFuZwogICAgaW50IFcgPSA1OyAvLyBrYXBhc2l0YXMgdGFzCgogICAgdmVjdG9yPGludD4gdmFsID0gezQsIDgsIDEwLCA3LCA4fTsKICAgIHZlY3RvcjxpbnQ+IHd0ICA9IHs3LCAxMCwgNSwgMTIsIDIwfTsKCiAgICBjb3V0IDw8ICJOaWxhaSBtYWtzaW11bSB5YW5nIGRhcGF0IGRpYmF3YSA9ICIgPDwga25hcFNhY2soVywgd3QsIHZhbCwgbikgPDwgZW5kbDsKICAgIHJldHVybiAwOwp9Cg==

MjA=

20