UVA-10163 Storage Keepers (0-1背包)

题目大意：有n个仓库，m个应聘者，每人对应一个能力值。一个人可以看多个仓库，一间仓库只能被一个人看。如果一个能力为p的人看k间仓库，那么安全系数为p/k，求出最大的最小安全系数，并且求出在此情况下所有人的能力值总和。

题目分析：这道题比较灵活，可以另仓库总数作为背包容量，也可以用应聘者总数作为背包容量。最后，求能力值总和时还需要再DP一次。

代码如下：

# include<iostream>

# include<cstring>

# include<cstdio>

# include<algorithm>

using namespace std;

const int INF=1000000000;

int n,m,p[35];

int dp[105][35];

int main()

{

    while(scanf("%d%d",&n,&m)&&n+m)

    {

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

            scanf("%d",p+i);

        memset(dp,0,sizeof(dp));

        for(int i=0;i<=m;++i) dp[0][i]=INF;

        for(int i=1;i<=n;++i){

            for(int j=1;j<=m;++j){

                dp[i][j]=dp[i][j-1];

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

                    dp[i][j]=max(min(dp[i-k][j-1],p[j]/k),dp[i][j]);

            }

        }

        printf("%d ",dp[n][m]);

        int ans1=dp[n][m];

        if(ans1==0){

            printf("0\n");

            continue;

        }

        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;++i) dp[i][0]=INF;

        for(int i=1;i<=n;++i){

            for(int j=1;j<=m;++j){

                dp[i][j]=dp[i][j-1];

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

                    if(p[j]/k>=ans1)

                        dp[i][j]=min(dp[i][j],dp[i-k][j-1]+p[j]);

            }

        }

        printf("%d\n",dp[n][m]);

    }

    return 0;

}

巴特西

UVA-10163 Storage Keepers (0-1背包)

最新文章

热门文章