Knapsck - 1

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
const int W = 1e5 + 5;
int w[N], v[N];
int dp[N][W];
int n, wt;

int dynamic(int pos, int we)
{

    if (we > wt)
        return INT_MIN;
    if (pos >= n)
        return 0;
    if (dp[pos][we] != -1)
        return dp[pos][we];
    int ans;
    ans = max(dynamic(pos + 1, we + w[pos]) + v[pos], dynamic(pos + 1, we));
    dp[pos][we] = ans;
    return ans;
}

int main() {
    cin >> n >> wt;
    memset(dp,-1,sizeof(dp));
    for (int i = 0; i < n; i++)
        cin >> w[i] >> v[i];
    cout << dynamic(0, 0);
}