hdu3466

题意：输入 N，M N：多少个测试用例 M：你手上拥有的钱


Pi，Qi，Vi Pi: 这件物品的价格 Qi：你手上钱M必须大于等于Qi才能买


Vi：这件物品的价值


输出 ：你能买到的东西的最大价值是多少？














这道题由于规定了手上的前低于q时就不能购买该样东西，所以要先将商品按q-p排序，剩下的就是简单的01背包了。


有什么不懂可以看看我以前写的01背包问题。

#include<iostream>
#include <cstdio>
#include <algorithm>
using namespace std;


struct calu
{
 int Pi, Qi,Vi;
}a[555];


int max(int a,int b)
{
 if(a>b)return a;
 else return b;
}


bool cmp(calu x,calu y)
{
 return x.Qi-x.Pi<y.Qi-y.Pi;
}


int main()
{
 int N,M,i,j,f[5555];
 while(scanf("%d",&N)!=EOF)
 {
  cin>>M;
  memset(f,0,sizeof(f));
  for(i=0;i<N;i++)
  {
   cin>>a[i].Pi>>a[i].Qi>>a[i].Vi;
  }
  sort(a,a+N,cmp);
   for(i=0;i<N;i++)
        {
            for(j=M;j>=a[i].Qi;j--)
            {
               f[j]=max(f[j],f[j-a[i].Pi]+a[i].Vi);
            }
   }
   cout<<f[M]<<endl;
 }
 return 0;
}


   
 附上一组测试用例


4 20
5 15 20
8 12 19
2 16 21
9 11 13


 


答案：60