我又来填坑了哈哈哈哈!!!!!

Description:

个物品,你有的金钱,对于每个物品,有三个参数求最大的价值和。


Solution:

我们考虑如果是要求买所有的物品,需要的总钱数最少是多少,那么我们只需要按从大到小排序,然后一个一个买就行了。那么我们考虑用同样的方法排序后背包 就行了。具体的证明就不说了,可以用排序不等式。
然后令表示考虑前个物品,已经使用了的金钱,可以得到的最大价值,如果满足


code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int N,M;
int F[5010]={0};

struct good_
{
    int P,Q,V;
}good[510]={{0,0,0}};

bool cmp(struct good_ a1,struct good_ a2)
{return a1.Q-a1.P>a2.Q-a2.P;}

int ans=0;

int main()
{
    for(;scanf("%d%d",&N,&M)!=EOF;)
    {
        for(int i=1;i<=N;i++)
            scanf("%d%d%d",&good[i].P,&good[i].Q,&good[i].V);
        sort(good+1,good+N+1,cmp);
        memset(F,0,sizeof(F));
        ans=0;
        for(int i=1;i<=N;i++)
        {
            for(int j=M-good[i].Q+good[i].P;j>=good[i].P;j--)
            {
                F[j]=max(F[j],F[j-good[i].P]+good[i].V);
                ans=max(F[j],ans);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}