PRACTICE
Link to the Practice problem can be found here
DIFFICULTY
Medium-Hard
PREREQUISITE
Dynamic Programming
PROBLEM
The basic DP Knapsack Problem. Where you’re given no. of Players and their Ratings. You need to find The Maximum Rating team which can be formed from a budget.
EXPLANATION
This is a standard DP Problem well known as 0-1 Knapsack.
`
for (int i = 1; i <= n; i++) {
table[i][0] = 0;
for(int w = 1; w <= c ; w++){
if (price[i-1] <= w){
table[i][w] = max(
rating[i-1] + table[i-1][w - price[i-1]],
table[i-1][w]
);
}
else{
table[i][w] = table[i-1][w];
}
}
}`
SOLUTION
Solution for the above problem can be found here