欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu3466

程序员文章站 2022-07-16 10:21:48
...


题意:输入 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
hdu3466