# hdu 4341 Gold miner(分组01双肩包)

www.MyException.Cn  网友分享于：2014-03-08  浏览：0次
hdu 4341 Gold miner(分组01背包)

http://acm.hdu.edu.cn/showproblem.php?pid=4341

```#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

int n,T;
struct node
{
int x,y;
int t,v;
bool operator < (const struct node &tmp)const
{

if(y*tmp.x == x*tmp.y)//斜率相等，按距离从小到大排序，不能按y/x排，因为x可能为0.
return y < tmp.y;
return y*tmp.x < x*tmp.y;
}
}point[210];

vector <struct node> edge[210];//保存分组后的状态
int cnt;
int dp[40010];

int solve()
{
memset(dp,0,sizeof(dp));
for(int i = 0; i <= cnt; i++)
{
for(int j = T; j >= edge[i][0].t; j--)
{
for(int k = 0; k < (int)edge[i].size(); k++)
dp[j] = max(dp[j], dp[j-edge[i][k].t]+edge[i][k].v);
}
}
return dp[T];
}

int main()
{
int item = 1;
while(~scanf("%d %d",&n,&T))
{
for(int i = 0; i < n; i++)
scanf("%d %d %d %d",&point[i].x,&point[i].y,&point[i].t,&point[i].v);

sort(point,point+n);

for(int i = 0; i < n; i++)
edge[i].clear();

cnt = 0;
edge[cnt].push_back(point[0]);

for(int i = 1; i < n; i++)	//n件物品分组
{
if(point[i].x*point[i-1].y == point[i].y*point[i-1].x)
edge[cnt].push_back(point[i]);
else edge[++cnt].push_back(point[i]);
}

for(int i = 0; i <= cnt; i++)
{
//修改同一条线上的金矿的时间和价值
for(int j = 1; j < (int)edge[i].size(); j++)
{
edge[i][j].t += edge[i][j-1].t;
edge[i][j].v += edge[i][j-1].v;
}
}
printf("Case %d: %d\n",item++,solve());
}
return 0;
}
```