首页 > ACM题库 > HDU-杭电 > HDU 4182-Help-or-else-背包问题-[解题报告]HOJ
2015
05-23

HDU 4182-Help-or-else-背包问题-[解题报告]HOJ

Help-or-else

问题描述 :

A penal colony for finance professionals will soon be holding its annual community service activity with some rules that are considered suitable for a penal colony. Every inmate is assigned a set P of N people to help with their finances and a limit of K minutes. In addition to the circumstances of the jth person, 1 <= j <= N, a time penalty of ej for choosing not to give advice and the time duration of dj minutes allotted to provide the advice are also made clear to the inmate. An inmate starts his community service at time T equal to zero. If the inmate started working with the jth person at time T, then he must terminate his work no later than T+dj. Regardless of the validity of the advice and time of completion, a value of Cj ( = T+ dj ) is deducted from the inmate’s alloted minutes. Also the inmate is not permitted to work with another person until the time T+ dj. If S is the set of people helped by an inmate, then the total number of used minutes is calculated as Insidious Branding
Your task is to write a program to calculate the maximum number of persons that can be helped by an inmate without exceeding his K minutes limit.

输入:

Input consists of sets for many inmates. The description for each inmate begins with two integers N and K, separated by a single space on a line by themselves, that represent the number of people and the maximum allowed minutes. 0 < N <= 200 and 0 < K <= 6000. Each of the following N lines contains two integers, separated by a single space, which represent the penalty and time duration one person to be assisted. All integers have values between 0 and 10000, inclusive. Input terminates with two zeros on a line by themselves.

输出:

Input consists of sets for many inmates. The description for each inmate begins with two integers N and K, separated by a single space on a line by themselves, that represent the number of people and the maximum allowed minutes. 0 < N <= 200 and 0 < K <= 6000. Each of the following N lines contains two integers, separated by a single space, which represent the penalty and time duration one person to be assisted. All integers have values between 0 and 10000, inclusive. Input terminates with two zeros on a line by themselves.

样例输入:

1 1000
100 1000
2 100
1000 1000
20 10
1 1
0 10000
4 293
61 30
295 39
206 27
94 85
0 0

样例输出:

1: 1
2: Mission Impossible
3: 0
4: 3

HDU 4182 Judges’ response(01背包+TSP状态压缩DP)

http://acm.hdu.edu.cn/showproblem.php?pid=4281

题意:本题有两问:首先是有n-1个物品,每个物品一个重量w,然后每个人有一个重量上限M,问你最小需要派几个人才能收集完所有物品.

第二问是:人和所有物品都有一个初始坐标,且人数无限制,在第一问的基础上,不超过人的负重的情况下,要拿走所有物品,人需要走多少路(人还要回到原点)?

分析:

       首先第一问:

我们先求出所有物品的组合状态st,如果st的总重<=M,那么它就是一个合法状态.然后用dp1[i]表示当收集了状态i的物品时,需要的最少人数.

这里的dp1[i]采用了滚动数组,其实应该是dp1[i][j]表示决策完前i个物品时,当前状态为j时需要的最少人数.

dp1[i][j+st]= min(dp1[i-1][j+st]  , dp1[i-1][j]+1)  st与j的交集为空(可以不为空,代码实现就不没考虑空),其实就算不为空也行..

且st=state[i],即st是第i个有效状态

初值为dp1[0][0]=0,其他dp1[0][j]=INF

 

dp1[i]=min(dp1[i],dp1[i-j]+1);   j是i的子集的合法状态

初始值:dp1[0]=0,其他dp1[i]=INF.

 

       第二问:

我们首先要求的是cost[i][j]表示当前在i点,走过的节点状态为j时需要走的总距离.其中这个j状态是第一问中计算的合法状态,并不是所有状态都算的.

cost[i][j+{k}] = min( cost[k][ j] +dist[i][k] )  其中k不属于j.

然后利用cost[i][j]可以求出np[j],np[j]就是从0点出发走过了j集合的点又回到0点的最小距离,其中j集合必定包含0,但是在程序代码中这点没体现出来.

其中np[j]= min( cost[i][j] ) 其中i属于集合j中.

最后我们合并np的结果.由于上一步计算的np[j]中的状态j都是包括了前置1,j&1!=0(想想为什么),所以后面把j分成两个子集的话,如果子集不带前置1,就直接可能为INF,导致结果错误.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define INF (1<<29)
int n,m;
int x[20],y[20],c[20];
int state[1<<17],cnt;//cnt表示合法状态有多少个,state[i]=x,表示第i个合法状态是x
bool isok[1<<17];
int dp1[1<<17],cost[17][1<<17];
int dist[20][20];
int np[1<<17];
bool good(int st)
{
    int sum=0;
    for(int i=0;i<n;i++)if(st&(1<<i))
        sum +=c[i];
    return sum<=m;
}
int solve_1()
{
    cnt=0;
    for(int i=0;i<(1<<n);i++)
    {
        isok[i]=good(i);
        if(isok[i]) state[cnt++]=i;
    }
    for(int i=0;i<(1<<n);i++)
        dp1[i]=INF;
    dp1[0]=0;
    for(int i=0;i<cnt;i++)
    {
        for(int j=(1<<n)-1;j>=0;j--)if(dp1[j]!=INF)
            dp1[j|state[i]]=min(dp1[j|state[i]],dp1[j]+1);
    }
    return dp1[(1<<n)-1];
}
int solve_2()
{
    //计算任意两点间的距离
    memset(dist,0,sizeof(dist));
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            dist[i][j]=dist[j][i]= ceil(sqrt((double)(x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j])));

    for(int i=0;i<n;i++)
        for(int j=0;j<(1<<n);j++)
            cost[i][j]=INF;//cost[i][j]表示当前在i点,已经走过了集合j中的点,所需要的最短距离
    cost[0][1]=0;

    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)if( (i&(1<<j)) )//j在集合i中
            for(int k=0;k<n;k++)if( (i&(1<<k))==0 )//k不在集合i中
                cost[k][i|(1<<k)] = min(cost[k][i|(1<<k)] , cost[j][i]+dist[j][k]);
    for(int i=0;i<(1<<n);i++)
    {
        np[i]=INF;
        if(isok[i])
        for(int j=0;j<n;j++)if(i&(1<<j))//j在集合i中
        {
            np[i] = min(np[i],cost[j][i]+dist[j][0]);//这里计算出来的有效np[i]的i&1都是!=0的
            //因为cost中的i&1 !=0
        }
    }
    for(int i=1;i<(1<<n);i++)
        if(i&1)for(int j=(i-1)&i;j;j=(j-1)&i)
        np[i]=min(np[i],np[j|1]+np[(i-j)|1]);//如果此处不|1的话,那么有可能分成的集合j和(i-j)因为没有前置1从而是INF的值
    return np[(1<<n)-1];
}
int main()
{

    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=0;i<n;i++)
            scanf("%d%d",&x[i],&y[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&c[i]);
        int ans1=solve_1();
        int ans2=solve_2();
        if(ans1==INF)
            printf("-1 -1\n");
        else
            printf("%d %d\n",ans1,ans2);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u013480600/article/details/22900387