0/1 knapsack

1// Your code here
2#include <iostream>
3#include <vector>
4using namespace std;
5 
6int knapsack(int W, vector<int> &wt, vector<int> &val, int n) {
7    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
8 
9    for (int i = 1; i <= n; i++) {
10        for (int w = 1; w <= W; w++) {
11            if (wt[i - 1] <= w) {
12                dp[i][w] = max(
13                    val[i - 1] + dp[i - 1][w - wt[i - 1]],
14                    dp[i - 1][w]
15                );
16            } else {
17                dp[i][w] = dp[i - 1][w];
18            }
19        }
20    }
21 
22    return dp[n][W];
23}
24 
25int main() {
26    int n, W;
27    cin >> n;
28 
29    vector<int> wt(n), val(n);
30 
31    for (int i = 0; i < n; i++)
32        cin >> wt[i];
33 
34    for (int i = 0; i < n; i++)
35        cin >> val[i];
36 
37    cin >> W;
38 
39    cout << knapsack(W, wt, val, n);
40 
41    return 0;
42}