学步园

需要排序的0-1背包

对物品按 qi-pi 的值从小到大排序，因为这样可以保证每次更新的状态值从小到大递增，前面更新过的状态不会影响后面更新的状态。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int max(int a,int b)
{
    if(a>b)return a;
    return b;
}
struct op
{
     int v,w,max;
}p[520];
int cmp(const void *a,const void *b)
{
    struct op *c,*d;
    c=(struct op *)a;
    d=(struct op *)b;
    return (c->max-c->v)-(d->max-d->v);
}
int main()
{
    int i,j,k,sum,n,m,dp[6000],d[6000];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<=m;i++){d[i]=m;dp[i]=0;}
        for(j=0,i=0;i<n;i++)
        {
            scanf("%d%d%d",&p[j].v,&p[j].max,&p[j].w);
            if(p[i].max>m)continue;
            j++;
        }
        n=j;
        qsort(p,n,sizeof(p[0]),cmp);
        for(i=1;i<=sum;i++)
            dp[i]=0;
        for(i=0;i<n;i++)
            for(j=m;j>=p[i].max;j--)
            {
                    if(dp[j]<dp[j-p[i].v]+p[i].w)
                    {
                    dp[j]=dp[j-p[i].v]+p[i].w;
                    }
            }
        printf("%d\n",dp[m]);
    }
    return 0;
}