15-12 Signing free-agent baseball players

Suppose that you are the general manager for a major-league baseball team. During the off-season, you need to sign some free-agent players for your team. The team owner has given you a budget of $\$X$ to spend on free agents. You are allowed to spend less than $\$X$ altogether, but the owner will fire you if you spend any more than $\$X$.

You are considering $N$ different positions, and for each position, $P$ free-agent players who play that position are available. Because you do not want to overload your roster with too many players at any position, for each position you may sign at most one free agent who plays that position. (If you do not sign any players at a particular position, then you plan to stick with the players you already have at that position.)

To determine how valuable a player is going to be, you decide to use a sabermetric statistic known as "$\text{VORP}$", or "value over replacement player". A player with a higher $\text{VORP}$ is more valuable than a player with a lower $\text{VORP}$. A player with a higher $\text{VORP}$ is not necessarily more expensive to sign than a player with a lower $\text{VORP}$, because factors other than a player's value determine how much it costs to sign him.

For each available free-agent player, you have three pieces of information:

• the player's position,
• the amount of money it will cost to sign the player, and
• the player's $\text{VORP}$.

Devise an algorithm that maximizes the total $\text{VORP}$ of the players you sign while spending no more than $\$X$ altogether. You may assume that each player signs for a multiple of $100,000$. Your algorithm should output the total $\text{VORP}$ of the players you sign, the total amount of money you spend, and a list of which players you sign. Analyze the running time and space requirement of your algorithm.

We will make an $N + 1$ by $X + 1$ by $P + 1$ table. The runtime of the algorithm is $O(NXP)$.

BASEBALL(N, X, P)
    initialize a table B of size (N + 1) by (X + 1)
    initialize an array P of length N
    for i = 0 to N
        B[i, 0] = 0
    for j = 1 to X
        B[0, j] = 0
    for i = 1 to N
        for j = 1 to X
            if j < i.cost
                B[i, j] = B[i - 1, j]
            q = B[i - 1, j]
            p = 0
            for k = 1 to P
                if j >= i.cost
                    t = B[i - 1, j - i.cost] + i.value
                    if t > q
                        q = t
                        p = k
            B[i, j] = q
            P[i] = p
    print("The total VORP is", B[N, X], "and the players are:")
    i = N
    j = X
    C = 0
    for k = 1 to N // prints the players from the table
        if B[i, j] != B[i - 1, j]
            print(P[i])
            j = j - i.cost
            C = C + i.cost
        i = i - 1
    print("The total cost is", C)