题解 P2066 【机器分配】

lenaalyth · 2018-05-05 20:22:58 · 题解

分组背包，扫了一眼好像没有一维背包写的。。所以发一下。。。其实也不算一维啦。。。。将公司获得的机器数当成重量，机器数为容量，每个公司为一组，然后直接用分组背包模板就可以了，因为数据较小，所以可以直接暴力得出结果。。。。代码如下

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
int dp[30],b,c,d,e[30][30],p[30][30];
int main()
{
    scanf("%d%d",&b,&c);
    for(int x=1;x<=b;x++)
    for(int y=1;y<=c;y++)
    {
        scanf("%d",&e[x][y]);
    }
    for(int x=1;x<=b;x++)//分组背包
    {
        for(int y=c;y>=1;y--)
        {
            for(int z=1;z<=y;z++)
            {
                    int v=dp[y];
                    dp[y]=max(dp[y],dp[y-z]+e[x][z]);
                    if(v!=dp[y])//暴力
                    {
                        for(int i=1;i<=b;i++)
                        {
                            p[y][i]=p[y-z][i];
                        }
                        p[y][x]=z;
                    }
                    else if(dp[y]==dp[y-z]+e[x][z])
                    {
                        int i;
                        for(i=1;i<=b;i++)
                        {
                            if(p[y][i]>p[y-z][i])
                            break;
                        }
                        if(i!=b)
                        {
                        for(i=1;i<=b;i++)
                        {   p[y][i]=p[y-z][i];}
                        p[y][x]=z;  
                        }
                    }
            }
        }
    }
    printf("%d\n",dp[c]);
    for(int x=1;x<=b;x++)
    {
        printf("%d %d\n",x,p[c][x]);
    }
    return 0;
}