[HDU 1171] 빅 이벤트 in HDU 모 함수 또는 멀 티 백 팩

http://acm.hdu.edu.cn/showproblem.php?pid=1171
제목: 항 전 컴퓨터 대학 은 분가 하여 물건 을 두 몫 으로 나 누 어 두 몫 의 가치 가 가장 가 까 워 야 한다.먼저 아 이 템 수량 n 을 입력 하면 n 개의 아 이 템 이 있 음 을 표시 하고 각 아 이 템 의 가치 와 수량 을 입력 합 니 다.구 덩이 를 비교 하 는 곳 은 입력 음수 가 끝 나 는 것 이다.
사고: 모 함수 또는 다 중 가방
모 함수 코드 (514 ms):

#include 
#include 
#include 

using namespace std;

int val[55],counts[55];
int nex[125005], temp[125005];

int main()
{
    int n;
    while(cin>>n && n >= 0)
    {
        int sum = 0;
        for(int i = 0; i < n; i++){
            cin>>val[i]>>counts[i];
            sum += val[i]*counts[i];
        }
        int avg = sum / 2;
        memset(nex, 0, sizeof(nex));
        memset(temp, 0, sizeof(temp));
        for(int i = 0; i <= counts[0]; i++){
            nex[i * val[0]] = 1;
        }
        int len = val[0] * counts[0];
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= len && j <= avg; j++){
                for(int k = 0; k <= val[i]*counts[i] && j+k <= avg; k += val[i]){
                    temp[j+k] += nex[j];
                }
            }
            len += val[i]*counts[i];
            for(int j = 0; j <= len && j <= avg; j++){
                nex[j] = temp[j];
                temp[j] = 0;
            }
        }
        for(int i= avg; i >= 0; i--){
            if(nex[i] != 0){
                cout<" "<break;
            }
        }
    }
    return 0;
}

다 중 가방 (93ms):

#include
#include
#include
#include
#include
#include

using namespace std;

int dp[125005];

void ZeroOnePack(int volume, int val, int vol)
{
    for(int i = volume; i >= vol; i--){
        dp[i] = dp[i-vol] + val;
    }
}

void CompletelyPack(int volume, int val, int vol)
{
    for(int i = vol; i <= volume; i++){
        dp[i] = dp[i-vol] + val;
    }
}

void MultiplePack(int volume, int val, int vol, int counts)
{
    if(vol * counts > volume)
        CompletelyPack(volume, val, vol);
    int mid = 1;
    while(mid <= counts){
        ZeroOnePack(volume, val*mid, vol*mid);
        counts = counts - mid;
        mid = mid << 1;
    }
    if(counts){
        ZeroOnePack(volume, val*counts, vol*counts);
    }
}

int main()
{
    int n;
    int val[55],counts[55];
    while(cin>>n && n >= 0)
    {
        int sum = 0;
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++){
            cin>>val[i]>>counts[i];
            sum += val[i]*counts[i];
        }
        for(int i = 0; i < n; i++){
            MultiplePack(sum/2, val[i], val[i],counts[i]);
        }
        cout<2]<<" "<2]<return 0;
}