HDu 3466 Proud Merchants 01リュックサック
1035 ワード
タイトルリンク: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]を小さいものから大きいものに並べ替えるべきである.
题意:买い物、それぞれのものは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;
}
}