DDream11·DSASDE-1DSA Round
Optimal Fantasy Team Selection Within Budget Cap (0/1 Knapsack Variant)
Problem
You are given n cricket players, each with a creditCost and predictedScore. You have a budget cap of 100 credits and must pick exactly 11 players to maximise total predicted score.
Example
players = [{cost:9.5, score:85}, {cost:8.0, score:70}, ...] (n=15)
budget = 100, teamSize = 11
Output: max predicted score and the selected team
Constraints
- 15 ≤ n ≤ 30
- 0 ≤ cost ≤ 15 (fractional)
- Additional constraint: at least 1 wicket-keeper, 3-5 batsmen, 1-3 all-rounders, 3-5 bowlers
Approach
Bounded knapsack DP with role constraints. With fractional credits, multiply all costs by 10 to convert to integers.
Follow-up
How would you extend this to return the top 10 team combinations by predicted score?
added 1 week ago