题目大意

已知有N名员工来应聘，每名员工有个3个属性，性别、价值和薪水。公司需要招聘X名男员工和Y名女员工。要求在满足总薪水不超过B的情况下，使得招聘的X+Y名员工总价值最大，且总薪水最少。需要输出字典序最小的方案。

解题思路

本题很明显的是一个背包问题。根据题目的数据范围，我们需要做的第一个优化就是将男女各作为一个背包问题分开处理。我们以男员工一个为例，女员工以相同的算法计算即可。同时题目要求输出方案，因此我们需要保留递推的过程。我们利用两个数组来完成：

f[i][j][k]：表示前i个男性员工中选择j个，总薪水恰好为k的价值。若不存在合法方案，价值为0。
g[i][j][k]：若f[i][j][k]存在合法方案，则g[i][j][k]表示该方案中最后选取的员工序号，否则为-1。

由此我们可以写出一个递推方程：

f[i][j][k] = max(
                f[i-1][j][k],
                // 不雇佣i号员工
                // 继承前一层的方案，此时 g[i][j][k] = g[i - 1][j][k]
                f[i-1][j-1][k-cost[i]]+value[i] | g[i-1][j-1][k-cost[i]] != -1
                // 雇佣i号员工
                // 需要保证g[i-1][j-1][k-cost[i]]存在合法方案
                // 此时g[i][j][k] = i
                )

写成伪代码为：

g[][][] = -1   // 初始化g数组均为 -1
f[][][] = 0    // 初始化f数组均为0
g[0][0][0] = 0 // 设定初始的合法方案
For i = 1 .. maleNum    // maleNum表示男性应聘者的数量
    For j = 0 .. X
        For k = 0 .. B
            f[i][j][k] = f[i - 1][j][k]
            g[i][j][k] = g[i - 1][j][k]
            If (j > 0 and k >= cost[i] && g[i-1][j-1][k-cost[i]] != -1 &&
                f[i][j][k] < f[i-1][j-1][k-cost[i]] + value[i]) Then
                f[i][j][k] = f[i-1][j-1][k-cost[i]] + value[i];
                g[i][j][k] = i
            End If
        End For
    End For
End For

最后我们得到的f[maleNum][X][v]表示在男性应聘者中选择X人，并且总薪水刚好为v的总价值。

接下来考虑，假设我们选取了一个f[maleNum][X][v]，我们如何来求出这个价值是由哪些员工构成的？

此时需要利用我们的g数组：

i = maleNum
j = X
k = v
while (j > 0) Then
    i = g[i][j][k]  
    // 获取当前合法方案的最后一个选取的员工
    // 因为此时的f[i][j][k]是从f[ g[i][j][k] ][j][k]转移过来的，
    // 因此直接令i = g[i][j][k]
    ansList.push(id[i]) // 将该员工的id加入答案序列
    j = j - 1
    k = k - cost[i]
    i = i - 1
    // 由于此时我们的f[i][j][k]是由f[i-1][j-1][k-cost[i]]转移的
    // 因此先回到f[i-1][j-1][k-cost[i]]
End While

这里存在一个问题，我们如何保证结果一定是最小字典序？有两个条件来保证：

1. 在我们对员工进行枚举时，优先枚举id字典序较小的员工
2. 在转移时我们要求f[i][j][k] < f[i-1][j-1][k-cost[i]] + value[i]时才进行。当有一个id为1,3(对应f[i-1][j][k])和1,4(对应f[i-1][j-1][k-cost[i]] + value[i])的合法方案同时存在，且总价值相等时，我们一定会优先选择1,3的方案。

通过以上的过程，我们可以求解出男女员工各自的背包结果。当给定v时，既可以求解出对应总薪水v的合法方案。

那么最后一步，如何将B的总薪水分配给男女两边？

这里我们仍然需要借助一个数组，不妨设为p[v]。p[v]表示总薪水不超过v时，获得最大价值的总薪水值。即p[v]等于max{f[maleNum][X][j] | j = 0 .. v}所对应的j，有多个值相等时，j取较小的一个。当f[maleNum][X][0 .. v]均不存在合法方案时，p[v] = -1。另外需要注意的是p数组需要计算p[0]。

这里我们给出一个通过递推求解p数组的方法：

p[] = -1
For i = 0 .. v
    If (i > 0) Then
        p[i] = p[i - 1]
    End If
    If (g[maleNum][X][i] != -1) Then
        If (p[i] == -1) Then
            p[i] = i
        Else
            If (f[ maleNum ][X][i] > f[ maleNum ][X][p[i]]) Then
                p[i] = i
            End If
        End If
    End If
End For

接下来我们用mp表示男员工的p数组，fp表示女员工的p数组，则最优结果的求解为：

maxValue = 0
maxCost = 0
For i = 0 .. B
    If (mp[i] != -1 && fp[B - i] != -1 &&  // 均存在合法方案   
        maxValue < mf[ maleNum ][X][mp[i]] + ff[ femaleNum ][Y][fp[B - i]]) Then
        maxValue = mf[ maleNum ][X][mp[i]] + ff[ femaleNum ][Y][fp[B - i]]
        maxCost = i
    End If
End For

男女员工选中的值分别为mf[ maleNum ][X][ mp[ maxCost ]]和ff[ femaleNum ][Y][fp[B - maxCost]]，根据上面给出的求解方案的办法即可得到最小字典序的方案。