HDU的大事件

浅浅的花香味﹌ 2022-05-27 06:27 138阅读 0赞

Problem Description：

如今，我们都知道计算机学院是HDU最大的部门。但是，也许你不知道计算机学院在2002年曾经被分成计算机学院和软件学院。这种分裂绝对是HDU中的一件大事！同时，这也是一件麻烦事。所有设施都必须减半。首先，评估所有设施，如果两个设施具有相同的价值，则认为两个设施相同。假定有N（0 <N <1000）种设施（不同的价值，不同的种类）。

Input：

输入包含多个测试用例。每个测试用例都以数字N开始（0 <N <= 50 - 不同设施的总数）。接下来的N行包含一个整数V（0 <V <= 50 - 设施值）和一个整数M（0 <M <= 100 - 对应的设施数量）。你可以假设所有的V都不相同。以负整数开始的测试用例会终止输入，并且不会处理该测试用例。

Output：

对于每种情况，打印一行包含两个整数A和B，分别表示计算机学院和软件学院的价值将分别得到。A和B应该尽可能相等。同时，你应该保证A不小于B.

Sample Input：

2  
10 1  
20 1  
3  
10 1  
20 2  
30 1

\-1

Sample Output：

20 10

40 40

思路：这道题可以用0-1背包。将所有设施的价值全部加起来，然后分成2组，要使这2组设施的价值尽可能相等，即要求它们2组的价值差要最小。那么我们可以首先将求价值总和的一半儿，然后先算其中一组的价值，此时价值总和的一半就相当于背包的最大容量，然后求不超过背包最大容量的情况下背包所能得到的最大价值，总价值-最大价值就是另一组设施的价值。要注意的是，这里每件物品的重量就是每件物品的价值。还要记住，每次的背包的N和V都要更新。

My DaiMa：

#include<stdio.h>
    #include<iostream>
    #include<string.h>
    using namespace std;
    int V,N,weight[10002],v[10002];
    long int f[100002];
    int OnePack()  //0-1背包的主要思想
    {
        memset(f,0,sizeof(f));
        for(int i=0;i<N;i++)
        {
            for(int j=V;j>=weight[i];j--)
                f[j]=max(f[j],f[j-weight[i]]+v[i]);
        }
        return f[V];
    }
    int main()
    {
        int t,a,b,x,y,z;
        while(scanf("%d",&t)&&t>0)
        {
            N=V=0;  //每次背包的N和V都要更新
            int i=0;
            while(t--)
            {
                scanf("%d%d",&a,&b);
                N+=b;
                V+=a*b;
                while(b--)
                {
                    v[i]=a;  //记录每件物品的价值
                    weight[i]=a;  //记录每件物品的重量
                    i++;
                }
            }
            z=V; 
            V/=2;
            x=max(OnePack(),z-OnePack());  //最大的设施价值放前面
            y=min(OnePack(),z-OnePack());
            cout<<x<<" "<<y<<endl;
        }
        return 0;
    }