Most Powerful Card: Find the Card Combination Maximizing Attack Under a Mana Cap

Question

## Problem

You have a collection of cards. Each card has a `mana_cost` and an `attack_power`. You can play cards whose total mana cost does not exceed `max_mana`. Maximize total attack power.

Return the maximum total attack power achievable.

```python
def max_attack(cards: list[dict], max_mana: int) -> int:
    # cards: [{"mana_cost": int, "attack_power": int}]
    pass
```

**Example:**
```
cards = [
  {"mana_cost": 3, "attack_power": 7},
  {"mana_cost": 2, "attack_power": 5},
  {"mana_cost": 4, "attack_power": 8},
  {"mana_cost": 1, "attack_power": 3}
]
max_mana = 5

Play card 1 (cost=3, atk=7) + card 4 (cost=1, atk=3) = mana 4, atk=10
Play card 2 (cost=2, atk=5) + card 4 (cost=1, atk=3) = mana 3, atk=8
Play card 3 (cost=4, atk=8) + card 4 (cost=1, atk=3) = mana 5, atk=11

Output: 11
```

## Approach

This is the 0/1 knapsack problem. Each card can be played at most once.

```python
dp = [0] * (max_mana + 1)
for card in cards:
    for m in range(max_mana, card["mana_cost"] - 1, -1):
        dp[m] = max(dp[m], dp[m - card["mana_cost"]] + card["attack_power"])
return dp[max_mana]
```

## Follow-ups

1. What is the time and space complexity of this DP solution?
2. What if cards can be played multiple times (unbounded knapsack)? How does the DP direction change?
3. Add a constraint: at most 3 cards total. How do you modify the DP state?
4. If max_mana is 10^9, the DP table is too large. What alternative approach would you use?

Most Powerful Card: Find the Card Combination Maximizing Attack Under a Mana Cap

Question Details

Full Details

About This Question

Topics

More Karat Interview Questions