#include<iostream>
#include<algorithm>

using namespace std;

const int MAXN = 40012;

int n,cnt;
bool dp[MAXN];
int h[MAXN],a[MAXN],c[MAXN],r[MAXN];

void ZeroOne_Pack(int w,int v)
{
    for(int i=v;i>=w;i--) if(dp[i-w]) dp[i]=true,cnt=max(cnt,i);
}
void Complete_Pack(int w,int v)
{
    for(int i=w;v>=i;i++) if(dp[i-w]) dp[i]=true,cnt=max(cnt,i);
}
void Multiple_Pack(int w,int n,int v)
{
    if(w*n>=v) Complete_Pack(w,v);
    else
    {
        for(int i=1;i<n;i*=2)
        {
            n-=i;
            ZeroOne_Pack(i*w,v);
        }
        ZeroOne_Pack(n*w,v);
    }
}
bool cmp(int i,int j)
{
    return a[i]<a[j];
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;
        int h_=0,a_=0,c_=0;
        memset(dp,false,sizeof(dp)); dp[0]=true;
        for(int i=0;n-i>0;i++)
        {
            scanf("%d %d %d",&h[i],&a[i],&c[i]);
            r[i]=i;
        }
        sort(r,r+n,cmp);
        for(int i=0;n-i>0;i++) Multiple_Pack(h[r[i]],c[r[i]],a[r[i]]);
        printf("%d\n",cnt);
    }
    return 0;
}

• Re:qsort WA sort AC 求解释，附170+MS代码 (1198) wolai 2012-09-08 20:33:55