题意：给你一些钱 m ， 共有 n 件物品，每件物品有价格 P，价值 V，还有一个很特别的属性 Q, Q 指你如过想买这件物品你的手中至少有这钱Q 。虽然你只要花费钱P，但你的手中至少有钱Q，如果不足Q，不能买。问给你钱M ，列出N件物品，最多能获得多少价值的东西。 思路：如果没Q的限制条件，这道题就是01背包水题。当我们要购买第i件物品，我们已经花费了j-p[i]，我们剩余的钱为m-(j-p[i])，我们要保证m-(j-p[i])>=q[i]；变换一下得p[i]<=j<=m+p[i]-q[i],所以我们只需要将物品按(p[i]-q[i])的大小升序排列就可以套用01背包了；
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> #include <queue> #include <stack> #define N 100005 #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define lc rt<<1 #define rc rt<<1|1 #define INF 0x3f3f3f3f using namespace std; const int maxn = 5005; const int mod = 1000000007; typedef long long ll; int n,m; struct node { int p,q,v; bool operator < (const node& r)const { return q - p < r.q - r.p; } }a[maxn]; int d[maxn]; int main() { //freopen("in","r",stdin); while(~scanf("%d%d",&n,&m)) { for(int i = 1; i <= n; ++i) { scanf("%d%d%d",&a[i].p, &a[i].q,&a[i].v); } sort(a+1,a+n+1); memset(d,0,sizeof(d)); int mx = 0; for(int i = 1; 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); } } printf("%d\n",d[m]); } }