HDU 1171 Big Event in HDU （多重bool背包） /（01背包）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1171

Big Event in HDU

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16791    Accepted Submission(s): 5908

Problem Description

Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).

 

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number of different facilities). The next N lines contain an integer V (0<V<=50 --value of facility) and an integer M (0<M<=100 --corresponding number of the facilities) each. You can assume that all V are different.
A test case starting with a negative integer terminates input and this test case is not to be processed.

 

Output

For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.

 

Sample Input

2

10 1

20 1

3

10 1

20 2

30 1

-1

 

Sample Output

20 10

40 40

 

解题方案：我的方案是把多重背包转化为01背包，背包的体积就是总和的一半，然后我们要尽可能的把背包放满：网上有大牛用母函数写的，比较一下差别：

Run ID	Submit Time	Judge Status	Pro.ID	Exe.Time	Exe.Memory	Code Len.	Language	Author
8310536	2013-05-15	Accepted	1171	31MS	392K	1295 B	G++	大牛的
8310472	2013-05-15	Accepted	1171	2125MS	1332K	837 B	G++	我的

那时间和内存开销差距！！！

我的解题代码：

// File Name: Big Event in HDU 1171.cpp
// Author: sheng
// Created Time: 2013年05月15日 星期三 19时53分07秒

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;

const int max_n = 5010;
int dp[250005];//数组大小50×100×50
int va[max_n];

int main ()
{
    int n, t, v;
    int sum;
    while (~scanf ("%d", &n) && n >= 0)
    {
        sum = 0;
        int cun = 0;
        memset (dp, 0, sizeof (dp));
        while (n--)
        {
            scanf ("%d %d", &v, &t);
            for (int i = 0; i < t; i ++)
            {
                va [cun++] = v;
            }
            sum += v*t;
        }
        for (int i = 0; i < cun; i ++)
        {
            for (int j = sum/2; j >= va[i]; j --)
            {
                dp[j] = max (dp[j], dp[j-va[i]] + va[i]);
            }
        }
        printf ("%d %d\n", sum - dp[sum/2], dp[sum/2]);
    }
    return 0;
}

大牛的代码：（以后再来理解） 模型：给出n个数，从中选出若干个数相加得到一个新数，求新数的集合

#include<iostream>
#include<stdio.h>
using namespace std;

//可以看作有a[i]张i元钱,i=1..n;尽量把它们分成相差最小的两份
//f[i]表示可否凑出i元,若有k元且f[i]==1->f[i+k]==1，因为只有一个转移状态,且状态可以叠加（不用清空再来），所以不必用2个数组，可以从后往前更新，
//若从前往后找有些更新的状态会干扰以后的状态 
const int N = 50;

bool f[250000/2+1];

int money[N+1],ge[N+1];

int main()
{
    int i,j,k,n,m,total,keep_total;
    while(scanf("%d", &n), n >= 0)
    {
        total = 0;
        for(i = 1; i <= n; i ++) 
        { 
            scanf("%d%d", money+i, ge+i); 
            total += money[i] * ge[i];
        }
        keep_total = total;
        total = total/2;         //若前半部分可以凑出，那么后半部分肯定可以，所以只要考虑前半部分就行了 
        for(i = 1; i <= total; i++)
            f[i] = 0;
        f[0] = 1;
        for( k = 1; k <= n; k ++)// 多少类
        {
            for(j = 1; j * 2 - 1 <= ge[k]; j = j * 2)   //每类几件,优化：只需让循环中取得的若干个j之和刚好可以表示从1..ge[k]的每个数，不可多一个，故用2进制 
            {
                for(i = total; i >= j * money[k]; i--)
                    f[i] |= f[i - j*money[k]];
            }
            j = ge[k] - (j-1);   //剩下的 
            if( j > 0)
            {
                for(i = total; i >= j * money[k]; i--)
                    f[i] |= f[i-j*money[k]];
            }
        }
        for(i = total; i >= 0; i --)
        {
            if( f[i] ) 
            {
                cout<<keep_total-i<<' '<<i<<endl;
                break;
            }
        }
    }
    return 0;
}