HDU 4341 分组背包

发表于 更新于 分类于 阅读次数：

分组背包，解决每一组物品只能选择一组的问题。

题目链接

题意

黄金矿工游戏，应该都玩过把，给你每个矿石的坐标，以及获取他的所需的时间以及你可以得到的价值，问你可以在规定时间内可以获得的最大价值。有个问题是，如果这两个矿石位于同一条直线上，必须是先把较近的矿石获取完毕才能获取后面的矿石。

思路

我们可以把位于同一条直线上的矿石合并，让较远的矿石的时间所需再加上等于他前面的矿石的时间之和，价值也是如此。那么这样的话，我们可以把位于同一条直线上的矿石看成一个组，我们每次只能在每个组中选取一种情况。这样就转换成了分组背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

typedef long long ll;
struct Point{
   int x, y, t, v;
   double k;
}P[10005];

bool cmp(Point a, Point b){
   if(a.k != b.k)
    return a.k < b.k;
   else{
     if(a.x != b.x)
        return a.y < b.y;
     else return a.y < b.y;
   }
}

int f[50005];
int vis[50005];
int main(){
     int N, T ,caser = 1;
     while(cin >>  N >> T){
        memset(vis, 0, sizeof(vis));
     for(int i = 1; i <= N; ++i){
        scanf("%d%d%d%d",&P[i].x,&P[i].y, &P[i].t, &P[i].v);
        P[i].k = (P[i].y * 1.0)/ P[i].x;
     }
     vector<int>a[505], b[505];
     sort(P + 1, P + N + 1,cmp);
     int tot = 0;
     memset(vis, 0, sizeof(vis));
     for(int i = 1; i <= N; ++i)
     {
         int sum1 = 0, sum2 = 0;
         sum1 += P[i].t;
         sum2 += P[i].v;
         if(!vis[i]){
         a[++tot].push_back(sum1);
         b[tot].push_back(sum2);
         vis[i] = 1;
         }
         for(int j = i + 1; j <= N; ++j){
            if(P[j].k != P[i].k)break;
            int t = P[j].t;
            int v = P[j].v;
            P[j].t += sum1;
            P[j].v += sum2;
            sum1 += t;
            sum2 += v;
            if(!vis[j]){
            vis[j] = 1;
            a[tot].push_back(P[j].t);
            b[tot].push_back(P[j].v);
            }
         }
     }
     memset(f, 0, sizeof(f));
     for(int i = 1; i <= tot; ++i){
        for(int j = T; j >= 0; --j){
            for(int k = 0; k < a[i].size(); ++k){
                if(j >= a[i][k])
                f[j] = max(f[j], f[j- a[i][k]] + b[i][k]);
            }
        }
     }
     cout << "Case " << caser++ << ": ";
     cout << f[T] << '\n';
     }
}