Server Investment: Maximize Throughput Within a Fixed Infrastructure Budget

Question

## Problem

You have a budget of `B` dollars and `n` server types, each with a cost and a throughput rating. You can buy multiple units of the same server type. Maximize total throughput without exceeding budget `B`.

This is an unbounded knapsack problem.

```python
from typing import List

def max_throughput(budget: int, servers: List[List[int]]) -> int:
    # servers: [[cost, throughput], ...]
    # return: maximum achievable total throughput
    pass
```

**Example:**
```
budget = 10
servers = [[3, 4], [5, 6], [2, 3]]

Buy 5x server[2] (cost=2, throughput=3): total cost=10, throughput=15
Or 2x server[0] + 1x server[2]: cost=8, throughput=11

Output: 15
```

## Approach

DP array `dp[b]` = max throughput with exactly budget `b`. Iterate each budget value; for each server, update `dp[b] = max(dp[b], dp[b - cost] + throughput)`. Time: O(B * n).

## Follow-ups

1. What if you can buy each server type at most once (0/1 knapsack)? How does the recurrence change?
2. How would you reconstruct the exact combination of servers chosen?
3. What if server costs and budgets are floating-point values — how do you adapt the DP?
4. If `B` is very large (10^9), what alternative approaches become necessary?

Server Investment: Maximize Throughput Within a Fixed Infrastructure Budget

Question Details

Full Details

Topics

More from Snowflake