rod cutting

// unbounded knapsack // only difference from 01 is that we can choose one element multiple times.
// rod cutting probelm
// here value array is price array and wt array is length array of rod
// knapsack is total length of rod
// sometimes wt array nahi di hogi to u can make one
int solve(vector<int> value , vector<int> wt , int knapsack){
    int  n = value.size();
    vector<vector<int>> dp (n+1 ,vecotr<int>(knapsack+1,0));
    // a represents the ath element .. b represents the knapsack present

    for(int a=1;a<=n;a++){
        for(int b=1;b<=knapsack;b++){
            if(wt[a-1]<=b){
            dp[a][b] = max(value[a-1]+dp[a][b-wt[a-1]] , dp[a-1][b]); //here we can choose ith element again
            }else{
            dp[a][b] = dp[a-1][b]; // cant choose the ath element becuase its weight is more
            }
        }
    }
    return dp[n][knapsack];

}