http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1675
/*
Description:
Altynai是一个纯正的DOTA菜鸟..而且他玩DOTA有一个特点,就是特别喜欢那些DPS(每秒输出的伤害)高的英雄..
而且买的装备也是专门买那种加攻击力加的很多的装备.. = =
现在他又在玩DOTA了..由于一开始杀了很多次敌方的英雄和小兵,Altynai现在身上有一些小钱了..
现在他开心的回自己的基地准备买装备了..由于有限制,他身上最多能带6个装备,而且每种装备他最多买一件..
由于时间紧迫,他必须抓紧时间来买装备,从而能使自己的攻击力增加的最多..当然了,Altynai不在意花了多少钱..
毕竟他最在意的是能增加的攻击力!
请你帮帮Altynai,算一下他能增加的最大的攻击力.
Input:
有多组数据,每组数据第一行为2个整数N和T(1<=N<=15,0<=T<=100000),表示基地装备的种类和Altynai现在身上有的钱。 接下去N行,每行有1个字符串s(1<=s长度<=20,只含有小写字母)和2个整数d和m(0<=d<=250,100<=m<=6000),分别表示每种武器的名字,增加的攻击力和价格。
Output:
算一下他能增加的最大的攻击力.
Sample Input:
6 100000
shengjian 250 6200
duijian 100 4450
yangdao 150 6666
budaofu 200 3000
hudie 180 4100
anmie 200 3500
Sample Output:
1080
*/
#include<iostream>
#include<string>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
/*Brute force*/
struct node
{
int cost,dps;
}a[16];
bool cmp(const node &a,const node&b)
{
if(a.dps!=b.dps)return a.dps>b.dps;
return a.cost<b.cost;
}
int main()
{
int n,fee,ans;
string s;
while(cin>>n>>fee)
{
ans=0;
for(int i=0;i<n;i++)
cin>>s>>a[i].dps>>a[i].cost;
sort(a,a+n,cmp);
for(int i1=0;i1<n;i1++)
{
int rmb1=fee,p1=0;
if(a[i1].cost>rmb1)continue;
if(a[i1].cost==rmb1)
{
p1+=a[i1].dps;
if(p1>ans)ans=p1;
continue;
}
rmb1-=a[i1].cost;
p1+=a[i1].dps;
if(p1>ans)ans=p1;
for(int i2=i1+1;i2<n;i2++)
{
int rmb2=rmb1,p2=p1;
if(a[i2].cost>rmb2)continue;
if(a[i2].cost==rmb2)
{
p2+=a[i2].dps;
if(p2>ans)ans=p2;
continue;
}
rmb2-=a[i2].cost;
p2+=a[i2].dps;
if(p2>ans)ans=p2;
for(int i3=i2+1;i3<n;i3++)
{
int rmb3=rmb2,p3=p2;
if(a[i3].cost>rmb3)continue;
if(a[i3].cost==rmb3)
{
p3+=a[i3].dps;
if(p3>ans)ans=p3;
continue;
}
rmb3-=a[i3].cost;
p3+=a[i3].dps;
if(p3>ans)ans=p3;
for(int i4=i3+1;i4<n;i4++)
{
int rmb4=rmb3,p4=p3;
if(a[i4].cost>rmb4)continue;
if(a[i4].cost==rmb4)
{
p4+=a[i4].dps;
if(p4>ans)ans=p4;
continue;
}
rmb4-=a[i4].cost;
p4+=a[i4].dps;
if(p4>ans)ans=p4;
for(int i5=i4+1;i5<n;i5++)
{
int rmb5=rmb4,p5=p4;
if(a[i5].cost>rmb5)continue;
if(a[i5].cost==rmb5)
{
p5+=a[i5].dps;
if(p5>ans)ans=p5;
continue;
}
rmb5-=a[i5].cost;
p5+=a[i5].dps;
if(p5>ans)ans=p5;
for(int i6=i5+1;i6<n;i6++)
{
int rmb6=rmb5,p6=p5;
if(a[i6].cost>rmb6)continue;
if(a[i6].cost==rmb6)
{
p6+=a[i6].dps;
if(p6>ans)ans=p6;
continue;
}
rmb6-=a[i6].cost;
p6+=a[i6].dps;
if(p6>ans)ans=p6;
}
}
}
}
}
}
cout<<ans<<endl;
}
}
#include<iostream>
#include<string>
using namespace std;
int n,fee,ans;
int dps[15],cost[15];
string s;
void DFS(int num,int mon,int att,int x)//num武器数 mon已用钱数 att现有攻击力 x上一件武器编号
{
if(num>6)return;
if(mon>fee)return;
if(att>ans){ans=att;}
for(int i=x+1;i<n;i++)
DFS(num+1,mon+cost[i],att+dps[i],i);
}
int main()
{
while(cin>>n>>fee)
{
ans=0;
for(int i=0;i<n;i++)
{
cin>>s>>dps[i]>>cost[i];
}
DFS(0,0,0,-1);
cout<<ans<<endl;
}
}