这道题最难搞的地方在于如何处理“小于qi时不能买”这一要求。苦思冥想许久，依然不知如何解决，于是只好去看题解......
这道题的做法是首先将“商人”按照q-p排序，然后再进行01背包。为什么是按照q-p排序呢？假设有两件物品A,B,他们对应的p,q分别是p1,q1和p2,q2。如果这两件东西都要买，那么，如果先买A，就至少需要p1 + q2的钱才能把两件东西都买到；如果先买B，就至少需要p2 + q1的钱才能把两件东西都买到。为了买到尽可能多的东西，获得尽可能大的价值，就应该按照代价小的方式来买。也就是说，假如先买A比先买B所需的代价更小，就有p1 + q2 < p2 + q1，即q1 - p1 < q2 - p2。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct{
int p,q,v;
}mer;
mer arr[505];
int dp[100000];
bool cmp(mer a,mer b)
{
return (a.q-a.p)<(b.q-b.p);
}
int main()
{
int n,m;
while(cin>>n>>m)
{
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
cin>>arr[i].p>>arr[i].q>>arr[i].v;
sort(arr,arr+n,cmp);
for(int i=0;i<n;i++)
for(int j=m;j>=arr[i].q;j--)
dp[j]=max(dp[j],dp[j-arr[i].p]+arr[i].v);
cout<<dp[m]<<endl;
}
return 0;
}