UVA10817-Headmaster's Headache-状态压缩的双肩包（记忆化搜索实现）

UVA10817-----Headmaster's Headache-----状态压缩的背包（记忆化搜索实现）

本文出自：http://blog.****.net/dr5459

题目地址：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1758

题目意思：

某校有n个教师和m个求职者。已知每人的工资和能交的课程集合，要求支付最少的工资使得每门课都至少有两名教师教学。在职教师必须招聘

解题思路：

因为课程的个数S最多才8个，我们可以想到用二进制压缩

例：

科目个数最多为8，用16位2进制数来表示。2进制中从右往左数，前8为表示有1位老师教该门课程，后8为表示有2位老师教（该位-8）的课程，

当s=8时，00000010 00000001表示1个老师教第一门课，2个老师教第2门课。这样 11111111 00000000 即为所要求的目标状态，代码中用T表示。

令dp[i][j]表示在前 j 个求职工中达到状态 i的最小花费。用st表示当前状态，则

dp[i][j] = min{dp[i][j], dp[i][j+1], dp[i+第j个人能够教的科目][j+1] +第j个人的工资}

定义函数int DP(int st,int i)表示第ｉ个人开始到ｎ个人结束，从状态 st 开始到目标状态的最小花费。这里用到记忆化搜索。

感谢：http://www.tuicool.com/articles/qMna2e

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<vector>
#include<iostream>
using namespace std;

const int maxn = 110;
const int maxs = 1<<16+1;

int s,m,n;
char stream[maxn];
int dp[maxn][maxs];
int value[maxn];
bool vis[maxn][maxs];
vector<int> lession[maxn];
int ALL;

int DP(int now,int x)
{
    if(vis[x][now])
        return dp[x][now];
    vis[x][now] = 1;

    if(now == ALL)
        return dp[x][now]=0;
    if(x==n)
        return 0x3f3f3f3f;

    int next = now;

    int len = lession[x].size();

    //cout<<"x "<<x<<endl;

    for(int i=0;i<len;i++)
    {
        int tmp = lession[x][i];
        //cout<<x<<" "<<i<<" "<<tmp<<endl;
        if((1<<(s+tmp)) & next)
            continue;
        if((1<<(tmp)) & next)
            next = next-(1<<tmp)+(1<<(s+tmp));
        else
            next = next+(1<<tmp);
    }

    if(next != now)
        dp[x][now] = min(dp[x][now],DP(next,x+1)+value[x]);
    dp[x][now] = min(dp[x][now],DP(now,x+1));

    return dp[x][now];
}


int main()
{
    while(~scanf("%d%d%d",&s,&m,&n) && s+m+n)
    {
        int sum = 0;
        int status = 0;
        memset(vis,false,sizeof(vis));
        memset(dp,0x3f3f3f3f,sizeof(dp));
        int tmp;
        for(int i=0;i<m;i++)
        {
            scanf("%d",&tmp);
            sum+=tmp;
            gets(stream);
            int len = strlen(stream);
            for(int j=0;j<len;j++)
            {
                sscanf(stream+j,"%d",&tmp);
                tmp--;//便于2进制
                //cout<<"tmp "<<tmp<<endl;
                while(isdigit(stream[j]))
                    j++;
                j++;
                if((1<<(s+tmp)) & status)
                    continue;
                if((1<<(tmp)) & status)
                {
                    status = status - (1<<(tmp)) + (1<<(s+tmp));
                }
                else
                    status = status + (1<<(tmp));
            }
        }

        for(int i=0;i<n;i++)
            lession[i].clear();

        for(int i=0;i<n;i++)
        {
            scanf("%d",&value[i]);
            gets(stream);
            int len = strlen(stream);
            for(int j=0;j<len;j++)
            {
                sscanf(stream+j,"%d",&tmp);
                tmp--;
                lession[i].push_back(tmp);
                while(isdigit(stream[j]))
                    j++;
                j++;
            }
        }

        ALL = 0;
        for(int i=s;i<2*s;i++)
        {
            ALL += (1<<i);
        }
        //cout<<ALL<<" "<<status<<endl;
        printf("%d\n",sum+DP(status,0));

    }
    return 0;
}

UVA10817-Headmaster's Headache-状态压缩的双肩包（记忆化搜索实现）

相关推荐