knapsack

#include <bits/stdc++.h>
#define MAX 10007

using namespace std;

int dp[MAX][MAX], pesos[MAX], val[MAX], p, v, dp2[MAX];

int knapsack(int pos, int pesoDisponivel){
    if(pos >= n) return 0;
    if(pesoDisponivel <= 0) return 0;
    if(dp[pos][pesoDisponivel] != -1) return dp[pos][pesoDisponivel];

    int inclue, naoInclue;

    if(pesos[pos] <= pesoDisponivel) inclue = knapsack(pos+1, pesoDisponivel - pesos[pos]) + val[pos];
    else inclue = 0;

    naoInclue = knapsack(pos+1, pesoDisponivel);
    return dp[pos][pesoDisponivel] = max(inclue, naoInclue);
}

int ubd(int general){
    for(int tam = 0; tam <= general; tam++){
        for(int item = 0; item < v; item++){
            if(pesos[item-1] <= tam) dp2[tam] = max(dp2[tam], dp2[tam-peso[item]] + val[item]);
        }
    }

    return dp2[general];
}
int main(){
    return 0;
}