Massive Algorithms: hihoCoder 1137-Recruitment

hihoCoder 1137-Recruitment | bitJoy > code

hihoCoder 1137-Recruitment | bitJoy > code
A company plans to recruit some new employees. There are N candidates (indexed from 1 to N) have taken the recruitment examination. After the examination, the well-estimated ability value as well as the expected salary per year of each candidate is collected by the Human Resource Department.
Now the company need to choose their new employees according to these data. To maximize the company's benefits, some principles should be followed:
1. There should be exactly X males and Y females.
2. The sum of salaries per year of the chosen candidates should not exceed the given budget B.
3. The sum of ability values of the chosen candidates should be maximum, without breaking the previous principles. Based on this, the sum of the salary per year should be minimum.
4. If there are multiple answers, choose the lexicographically smallest one. In other words, you should minimize the smallest index of the chosen candidates; If there are still multiple answers, then minimize the second smallest index; If still multiple answers, then minimize the third smallest one; ...
Your task is to help the company choose the new employees from those candidates.
输入
The first line contains four integers N, X, Y, and B, separated by a single space. The meanings of all these variables are showed in the description above. 1 <= N <= 100, 0 <= X <= N, 0 <= Y <= N, 1 <= X + Y <= N, 1 <= B <= 1000.
Then follows N lines. The i-th line contains the data of the i-th candidate: a character G, and two integers V and S, separated by a single space. G indicates the gender (either "M" for male, or "F" for female), V is the well-estimated ability value and S is the expected salary per year of this candidate. 1 <= V <= 10000, 0 <= S <= 10.
We assure that there is always at least one possible answer.
输出
On the first line, output the sum of ability values and the sum of salaries per year of the chosen candidates, separated by a single space.
On the second line, output the indexes of the chosen candidates in ascending order, separated by a single space.
样例输入
4 1 1 10
F 2 3
M 7 6
M 3 2
F 9 9
样例输出
9 9
1 2

https://ericfu.me/hihocoder-1137-recruitment/

很容易想到，这题是01背包问题的一个变体。基本思路是分别对男、女集合做01背包。几个难点：

男、女分开的预算不知道，只有一个总的预算，怎么办？——把B作为总预算，然而DP的结果其实是包含0~B各个情况的，所以我们可以通过一个B*B的循环，枚举（0, 0）,（0, 1）……（B, B）所有的预算分配方式，找出价值最大的。
男女人数必须为X，Y——这也看作一个限制条件：每个人的代价是1。所以这里的动归其实是三维的。
输出的不仅是总价值还要具体方案——这个很复杂，必须回溯。回溯意味着要保存下DP的所有过程，要么直接开三维数组（不压缩），要么用二维数组、但是额外用一个布尔型三维数组保存每次的处理方式（选择该人还是不选）

DP初始子问题的设定非常重要！！初始子问题的行（设为0）或不行（设为一个负数，例如-1000000000）将决定整个DP过程，这对所有背包问题都适用。本题中，我们设定：男女人数必须是恰好相等的，所以人数k > 0的初始子问题被初始化为-1000000000；总预算不一定要恰好，因为我们后期反正还会选出总预算最小的。

int N, B;  
char G;  
struct FM {  
    int n;
    int no[100];
    int value[100];
    int cost[100];
    int dp[1024][101];
    bool select[1024][1024][101];
    int limit;
} mm, gg;

void zero_one_pack(struct FM& fm) {

    for (int i = 0; i <= B; i++)
        for (int j = 0; j <= fm.limit; j++)
            fm.dp[i][j] = -1000000000;
    fm.dp[0][0] = 0;

    for (int i = fm.n - 1; i >= 0; i--) {
        for (int j = B; j >= fm.cost[i]; j--) {
            for (int k = fm.limit; k >= 1; k--) {
                int value = fm.dp[j - fm.cost[i]][k - 1] + fm.value[i];
                if (value >= fm.dp[j][k]) {
                    fm.dp[j][k] = value;
                    fm.select[i][j][k] = true;
                }
            }
        }
    }
}

vector<int> seq;  
bool get_result(struct FM &fm, int s, int k, int i) {  
    if (s == 0 && k == 0) return true;
    for (; i < fm.n; i++) {
        if (fm.select[i][s][k]) {
            seq.push_back(fm.no[i]);
            if (get_result(fm, s - fm.cost[i], k - 1, i + 1)) return true;
            seq.pop_back();
        }
    }
}

vector<int> merge(vector<int> &a, vector<int> &b) {  
    vector<int> result;
    int i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        if (a[i] < b[j]) {
            result.push_back(a[i++]);
        }
        else {
            result.push_back(b[j++]);
        }
    }
    while (i < a.size()) result.push_back(a[i++]);
    while (j < b.size()) result.push_back(b[j++]);
    return result;
}

int main() {  
    scanf("%d %d %d %d", &N, &gg.limit, &mm.limit, &B);
    for (int i = 1; i <= N; i++) {
        scanf("%c", &G);
        if (G == 'F') {
            int j = mm.n++;
            scanf("%d %d", &mm.value[j], &mm.cost[j]);
            mm.no[j] = i;
        }
        else if (G == 'M') {
            int j = gg.n++;
            scanf("%d %d", &gg.value[j], &gg.cost[j]);
            gg.no[j] = i;
        }
        else {
            i--;
            continue;
        }
    }
    zero_one_pack(mm);
    zero_one_pack(gg);
    int max_value = -1, min_cost = INT_MAX;
    vector<pair<int, int>> ijs;
    for (int i = 0; i <= B; i++) {
        for (int j = 0; j <= B - i; j++) {
            int value = gg.dp[i][gg.limit] + mm.dp[j][mm.limit];
            if (value >= max_value) {
                if (value > max_value || i + j < min_cost) {
                    max_value = value;
                    min_cost = i + j;
                    ijs.clear();
                    ijs.push_back(pair<int, int>(i, j));
                }
                else if (i + j == min_cost) {
                    ijs.push_back(pair<int, int>(i, j));
                }
            }
        }
    }
    printf("%d %d\n", max_value, min_cost);
    vector<int> candidate(1, INT_MAX);
    for (auto &ij : ijs) {
        seq.clear();
        get_result(gg, ij.first, gg.limit, 0);
        auto rgg = seq;
        seq.clear();
        get_result(mm, ij.second, mm.limit, 0);
        auto rmm = seq;
        auto merged = merge(rgg, rmm);
        if (merged < candidate) candidate = merged;
    }
    for (int i = 0; i < candidate.size(); i++) {
        printf("%d%c", candidate[i], i == candidate.size() - 1 ? '\n' : ' ');
    }

本题实质上是一个0/1背包问题，将男性和女性分别背包。
以男性为例，转换为从若干个（n1）人中取出X个男性，保证他们的工资总和不超过B，但最大化能力总和。每个应聘者相当于一个物品，工资总和为B相当于容量为B的背包。常规的0/1背包是从这n1个应聘者中挑任意多个，使得工资总和不超过B，但能力总和最大。但是本题的背包限定了取且只取X个应聘者，使得工资总和不超过B，但能力总和最大。
DP的状态转移过程为：假设dpm[i][j]表示从【当前】所有男性中选取i个，工资总和为j时获得的最大能力总和。
假设X=5，当前正好来了5个男性，已经求到了dpm[X][j]，当再来一位男性应聘者a（能力为v，工资为s）时，dpm[X][j]含义就是从当前6位应聘者中选5位满足限定条件。此时有两个选择，要或者不要a，如果不要a，则dpm[X][j]结果不变；如果要a，则前5个只能取4个，加上a就是5个，此时能力总和就是dpm[X-1][j-s]+v，所以最终dpm[X][j]=max{dpm[X][j], dpm[X-1][j-s]+v}。
当把所有男性应聘者都测试过之后，dpm[X][j]就是从所有n1个男性中选X个，其工资总和为j时的能力总和。
最后把男性和女性的情况一组合，再满足总预算不超过B，取全局最优结果。
因为应聘者N最多为100，所以使用数组unsigned long long id[2]来记录应聘者选取情况，unsigned long long 为64位，每位二进制代表一名应聘者，为1选中，id[0]记录前50位，id[1]记录后50位。

const int kMaxN = 105, kMaxB = 1005;

int dpf[kMaxN][kMaxB], dpm[kMaxN][kMaxB];//dpf[i][j]从所有女性应聘者中选取i个，工资总和为j时的最大能力和

unsigned long long idf[kMaxN][kMaxB][2];//记录女性选取情况

unsigned long long idm[kMaxN][kMaxB][2];//记录男性选取情况

int N, X, Y, B, V, S;

char G[2];

int ans_v = 0, ans_s = 0;//总能力，总工资

unsigned long long ans_id[2] = { 0 };//总选取情况

void DP()

{

    dpf[0][0] = dpm[0][0] = 0;

    int cnt_f = 0, cnt_m = 0, sum_s = 0;

    for (int i = 1; i <= N; i++)

{

        scanf("%s %d %d", G, &V, &S);

        sum_s += S;

        sum_s = min(sum_s, B);

        if (G[0] == 'F')

{

            cnt_f++;

            cnt_f = min(cnt_f, Y);//最多选取Y位

            for (int j = cnt_f; j >= 1; j--)

{

                for (int k = sum_s; k >= S; k--)

{

                    if (dpf[j - 1][k - S] < 0)

                        continue;

                    if (dpf[j - 1][k - S] + V > dpf[j][k])

{

                        dpf[j][k] = dpf[j - 1][k - S] + V;

                        idf[j][k][0] = idf[j - 1][k - S][0];

                        idf[j][k][1] = idf[j - 1][k - S][1];

                        if (i <= 50)

                            idf[j][k][0] |= 1LL << (i - 1);//选中第i位

                        else

                            idf[j][k][1] |= 1LL << (i - 1 - 50);//选中第i位

}

}

}

}

        else

{

            cnt_m++;

            cnt_m = min(cnt_m, X);

            for (int j = cnt_m; j >= 1; j--)

{

                for (int k = sum_s; k >= S; k--)

{

                    if (dpm[j - 1][k - S] < 0)

                        continue;

                    if (dpm[j - 1][k - S] + V > dpm[j][k])

{

                        dpm[j][k] = dpm[j - 1][k - S] + V;

                        idm[j][k][0] = idm[j - 1][k - S][0];

                        idm[j][k][1] = idm[j - 1][k - S][1];

                        if (i <= 50)

                            idm[j][k][0] |= 1LL << (i - 1);

                        else

                            idm[j][k][1] |= 1LL << (i - 1 - 50);

}

}

}

}

}

}

void Match()

{

    for (int i = 0; i <= B; i++)

{

        if (dpf[Y][i] == -1)

            continue;

        for (int j = 0; j + i <= B; j++)

{

            if (dpm[X][j] == -1)

                continue;

            if (dpf[Y][i] + dpm[X][j] > ans_v)//能力更强

{

                ans_v = dpf[Y][i] + dpm[X][j];

                ans_s = i + j;

                ans_id[0] = idf[Y][i][0] | idm[X][j][0];

                ans_id[1] = idf[Y][i][1] | idm[X][j][1];

}

            else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) < ans_s)//能力相同，但工资更少

{

                ans_s = i + j;

                ans_id[0] = idf[Y][i][0] | idm[X][j][0];

                ans_id[1] = idf[Y][i][1] | idm[X][j][1];

}

            else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) == ans_s)//能力和工资都相同

{

                int id0 = idf[Y][i][0] | idm[X][j][0];

                int id1 = idf[Y][i][1] | idm[X][j][1];

                if (ans_id[0] > id0)//排序靠前

{

                    ans_id[0] = id0;

                    ans_id[1] = id1;

}

                else if (ans_id[1] > id1)//排序靠前

{

                    ans_id[0] = id0;

                    ans_id[1] = id1;

}

}

}

}

}

void FormatOut()

{

    printf("%d %d\n", ans_v, ans_s);

    for (int i = 1; i <= 50; i++)

{

        if (ans_id[0] & 1)

            printf("%d ", i);

        ans_id[0] >>= 1;

}

    for (int i = 51; i <= 100; i++)

{

        if (ans_id[1] & 1)

            printf("%d ", i);

        ans_id[1] >>= 1;

}

}

int main()

{

    memset(dpf, -1, sizeof(dpf));

    memset(dpm, -1, sizeof(dpm));

    memset(idf, 0, sizeof(idf));

    memset(idm, 0, sizeof(idm));

    scanf("%d %d %d %d", &N, &X, &Y, &B);

    DP();

    Match();

    FormatOut();

    return 0;

}

http://blog.csdn.net/elicococoo/article/details/45269611
这个题显然就是个dp，关键在dp的技巧上。

思路：男女分别dp，然后匹配。

做两个dp，dpf[i][j]表示所有女性中选i个，工资为j时的价值，dpm[i][j]表示所有男性中选i个，工资为j时的价值；fidx[i][j][0]，i j表示之前的dpf[i][j]，0是所有应聘人的前50个，1是后50个，这是个long long数组，利用位运算来标记对应i j选了哪些人，midx同理。

设要选female个女性，male个男性，对所有的dpf[female][i]和dpm[male][j]匹配，根据题意选出B以下价值最大工资最低字典序最靠前的。

http://m.blog.csdn.net/blog/fuyufjh/48106847
https://github.com/tandztc/HihoCoder/blob/master/Problem1137.cs
public static void MyMain(string[] args)
{
string[] tokens = Console.ReadLine().Split(' ');
int N = int.Parse(tokens[0]);
int X = int.Parse(tokens[1]);
int Y = int.Parse(tokens[2]);
int B = int.Parse(tokens[3]);

int[,] dpmale = new int[X + 1, B + 1]; //dpmale[i,j]表示选i名男应聘者在预算为j的情况下的最大分数，下同
int[,] dpfemale = new int[Y + 1, B + 1];
BitArray[,] dpmalebit = new BitArray[X + 1, B + 1]; //dpmalebit[i,j]表示入选男性的数组，true表示录用，下同
BitArray[,] dpfemalebit = new BitArray[X + 1, B + 1]; //dpmalebit[i,j]表示入选男性的数组，true表示录用，下同
for (int i = 0; i < X+1; i++)
{
for (int j = 0; j < B+1; j++)
{
dpmale[i, j] = -1;
dpmalebit[i, j] = new BitArray(N); //这里的大小为n，因为男女可以出现在任何序号，最后的结果有用Or合并即可
}
}
for (int i = 0; i < Y + 1; i++)
{
for (int j = 0; j < B + 1; j++)
{
dpfemale[i, j] = -1;
dpfemalebit[i, j] = new BitArray(N);
}
}
dpmale[0, 0] = 0;
dpfemale[0, 0] = 0;
int malecnt = 0, femalecnt = 0, malebgt = 0, femalebgt = 0;
for (int i = 0; i < N; i++)
{
string[] interviewer = Console.ReadLine().Split(' ');
string G = interviewer[0];
int V = int.Parse(interviewer[1]);
int S = int.Parse(interviewer[2]);
if (G=="M")
{
malecnt++;
malebgt += S;
int realcnt = Math.Min(malecnt, X);
int realbgt = Math.Min(malebgt, B);
for (int curcnt = realcnt; curcnt >0 ; curcnt--)
{
for (int curbgt = realbgt; curbgt >= S; curbgt--)
{
if (dpmale[curcnt - 1, curbgt - S] == -1)
{
continue;
}
if (dpmale[curcnt - 1, curbgt - S] + V > dpmale[curcnt, curbgt])
{
dpmale[curcnt, curbgt] = dpmale[curcnt - 1, curbgt - S] + V;
dpmalebit[curcnt, curbgt].SetAll(false);
dpmalebit[curcnt, curbgt].Or(dpmalebit[curcnt - 1, curbgt - S]);
dpmalebit[curcnt, curbgt].Set(i, true);
}
}
}
}
else
{
femalecnt++;
femalebgt += S;
int realcnt = Math.Min(femalecnt, Y);
int realbgt = Math.Min(femalebgt, B);
for (int curcnt = realcnt; curcnt > 0; curcnt--)
{
for (int curbgt = realbgt; curbgt >= S; curbgt--)
{
if (dpfemale[curcnt - 1, curbgt - S] == -1)
{
continue;
}
if (dpfemale[curcnt - 1, curbgt - S] + V > dpfemale[curcnt, curbgt])
{
dpfemale[curcnt, curbgt] = dpfemale[curcnt - 1, curbgt - S] + V;
dpfemalebit[curcnt, curbgt].SetAll(false);
dpfemalebit[curcnt, curbgt].Or(dpfemalebit[curcnt - 1, curbgt - S]);
dpfemalebit[curcnt, curbgt].Set(i, true);
}
}
}
}
}

//遍历每种预算匹配，得到预算不超过B的情况下的最大分数
int maxpoint = 0, minbudget = B, maleselect = -1, femaleselect = -1;
for (int i = 0; i <= B; i++)
{
if (dpmale[X,i]==-1)
{
continue;
}
for (int j = 0; j <= B-i; j++)
{
if (dpfemale[Y,j] == -1)
{
continue;
}
if (dpmale[X, i] + dpfemale[Y, j] > maxpoint)
{
maxpoint = dpmale[X, i] + dpfemale[Y, j]; //这一句提交到hihocoder的时候会runtime error
maleselect = i;
femaleselect = j;
minbudget = i + j;
}
else
{
continue;
if (dpmale[X, i] + dpfemale[Y, j] == maxpoint)
{
if (minbudget > i + j)
{
maleselect = i;
femaleselect = j;
minbudget = i + j;
}
else if (minbudget == i + j)
{
BitArray former = new BitArray(dpmalebit[X, maleselect].Or(dpfemalebit[Y, femaleselect]));
BitArray current = new BitArray(dpmalebit[X, i].Or(dpfemalebit[Y, j]));
for (int k = 0; k < N; k++)
{
if (former[k] ^ current[k])
{
if (current[k])
{
maleselect = i;
femaleselect = j;
}
break;
}
}
}
}
}
}
}
Console.WriteLine("{0} {1}", maxpoint, minbudget);
if (maleselect==-1 || femaleselect == -1)
{
return;
}
BitArray result = new BitArray(dpmalebit[X, maleselect].Or(dpfemalebit[Y, femaleselect]));
bool flag = false;
for (int i = 0; i < N; i++)
{
if (result[i])
{
if (flag)
{
Console.Write(" ");
}
flag = true;
Console.Write(i+1);
}
}
Console.WriteLine();
}
}
Read full article from hihoCoder 1137-Recruitment | bitJoy > code

hihoCoder 1137-Recruitment | bitJoy > code

Labels

Popular Posts