#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int knapsack(int W, vector<int> wt, vector<int> val, int n) {
    vector<vector<int>> K(n+1, vector<int>(W+1, 0));
    for(int i=1;i<=n;i++){
        for(int w=1;w<=W;w++){
            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, W=20;
    vector<int> val={5,7,8,10,12};
    vector<int> wt ={5,4,7,10,8};
 
    cout<<"Hasil maksimum: "<<knapsack(W,wt,val,n)<<endl;
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGtuYXBzYWNrKGludCBXLCB2ZWN0b3I8aW50PiB3dCwgdmVjdG9yPGludD4gdmFsLCBpbnQgbikgewogICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBLKG4rMSwgdmVjdG9yPGludD4oVysxLCAwKSk7CiAgICBmb3IoaW50IGk9MTtpPD1uO2krKyl7CiAgICAgICAgZm9yKGludCB3PTE7dzw9Vzt3KyspewogICAgICAgICAgICBpZih3dFtpLTFdPD13KQogICAgICAgICAgICAgICAgS1tpXVt3XT1tYXgodmFsW2ktMV0rS1tpLTFdW3ctd3RbaS0xXV0sS1tpLTFdW3ddKTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgS1tpXVt3XT1LW2ktMV1bd107CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIEtbbl1bV107Cn0KCmludCBtYWluKCl7CiAgICBpbnQgbj01LCBXPTIwOwogICAgdmVjdG9yPGludD4gdmFsPXs1LDcsOCwxMCwxMn07CiAgICB2ZWN0b3I8aW50PiB3dCA9ezUsNCw3LDEwLDh9OwoKICAgIGNvdXQ8PCJIYXNpbCBtYWtzaW11bTogIjw8a25hcHNhY2soVyx3dCx2YWwsbik8PGVuZGw7CiAgICByZXR1cm4gMDsKfQo=

NSAKNSA0IDcgOCAxMCAKMTAgNSA3IDEyIDggCjIw

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