HDu 3466 Proud Merchants 01リュックサック

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3466
题意:买い物、それぞれのものは3つの特徴値があって、pは価格を代表して、qはあなたの手の中のお金がqを下回らなければこの品物を买うことができなくて、vは得た価値を代表して、手の中のお金で买う最大の価値を求めます.
によって   f[j]=max(f[j],f[j-p[i]]+v[i])   このときf[j−p[i]]は既に計算されている必要がある.一方、各物品iについては、j-p[i]が最小q[i]-p[i]となるべきである .したがって、q[i]-p[i]を小さいものから大きいものに並べ替えるべきである.

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 5500

using namespace std;

struct node
{
    int q,p,v;
}a[N];

int d[N];

bool cmp(node a,node b)
{
    return a.q-a.p<b.q-b.p;
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0;i<n;i++)
            scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);
        sort(a,a+n,cmp);
        memset(d,0,sizeof(d));
        for(int i=0;i<n;i++)
            for(int j=m;j>=a[i].q;j--)
                d[j]=max(d[j],d[j-a[i].p]+a[i].v);
        cout<<d[m]<<endl;
    }
}