hdu 1171 Big Event in HDU

题意:给定N种物品的价值v和数量num;要你尽可能实现二分，输出a,b(a>=b);种类最多50种，每种价值和个数均不超过50；

分析:离线算法，以总价值的一般为V(背包的容量)，去装下最大重量的物品即b，这样其补就是a;

V最大为1e5的数量级，N<=50,n[i]<=50;来分析下时间复杂度；

将多重背包分解为完全背包和多重背包；

如果该物品符合完全背包，易知为O(V);如果该物品为01背包，使用二进制优化之后时间复杂度为O(V*log(n[i]));(这就为什么存在使用单调队列使得总复杂度为O(V*N)的算法)

109MS 1816K

#include<bits/stdc++.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define inf 0x3f3f3f3f
int w[55],num[55],V;
int f[125005];
void ZeroOnePack(int w,int num)
{
    for(int v = V;v >= w;v--)
        f[v] = max(f[v],f[v-w]+w);
}
void CompletePack(int w,int num)
{
    for(int v = w;v <= V;v++)
        f[v] = max(f[v],f[v-w]+w);
}
void MultiPack(int w,int num)
{
    if(w*num >= V)
        CompletePack(w,num);
    else{
        for(int k = 1;k < num;k <<= 1){
            ZeroOnePack(w*k,k*w);
            num -= k;
        }
        ZeroOnePack(w*num,num*w);
    }
}
int main()
{
    int N;
    while(scanf("%d",&N) == 1 && N >= 0){
        int sum = 0;
        rep1(i,1,N){
            scanf("%d%d",w+i,num+i);
            sum += w[i]*num[i];
        }
        V = sum>>1;
        fill(f,f+V+1,0);
        rep1(i,1,N){
            MultiPack(w[i],num[i]);
        }
        printf("%d %d
",sum - f[V],f[V]);
    }
}

View Code

解法2:将物品转化为01背包，即将每种物品直接分解成n[i]件价值和重量(其实是相等的)物品；之后使用朴素的01背包，时间复杂度为O(V*Σⁿ₁(n[i]));Σⁿ₁(n[i]) <= 2500;也是可以承受的；

1045MS 1836K

#include<bits/stdc++.h>
using namespace std;

int a[5005],Q[125005];
int main()
{
    int cs,v,num;
    while(scanf("%d",&cs) == 1 && cs >= 0){
        int sub = 0,sum = 0;
        for(int j = 1;j <= cs;j++){
            scanf("%d%d",&v,&num);
            sum += v*num;
            for(int i=1;i <= num;i++)//将多重背包转化成单重背包；
                a[++sub] = v;
        }
        int V = sum>>1;
        fill(Q,Q+V+1,0);
        for(int k = 1;k <= sub;k++)
            for(int j = V;j >= a[k];j--)
                Q[j] = max(Q[j],Q[j-a[k]]+a[k]);
        printf("%d %d
",sum-Q[V],Q[V]);
    }
    return 0;
}

View Code