HDU 3244 完全背包 + 二分

发表于 分类于 阅读次数：

本以为是道简单的二分，WA到哭。

题意

一个人要邀请同学来玩，然后需要准备N种材料，每一行有6个数字，分别代表一个人需要多少个这样的材料，以及这个人已经有的材料个数，再就是两种包装，一种小袋子的，有它的size和需要的花费，一种大袋子的，也有size和花费，现在问你这个人最多能够招待多少人。

思路

二分人数，但是需要大约估计出一个上限，否则会超时。另一个在统计需要怎么分配小袋子和大袋子才能在最小花费的情况下得到最大价值，需要用完全背包。注意的是f数组的初始值是Inf,但是这个数组太大，我们也仅仅需要把一部分赋值成inf,这里可以用for循环，如果f全都赋值inf,会超时。

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
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <math.h>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
#define pi acos(-1.0)
int n,s;
const int maxn = 105;
int x[maxn],y[maxn],s1[maxn],s2[maxn],p1[maxn],p2[maxn];
int f[8000005];
int S[2],P[2];
int cal(int num, int data, int need)
{
    S[0] = s1[num];
    S[1] = s2[num];
    P[0] = p1[num];
    P[1] = p2[num];
    int v = need +  s2[num];
    for(int i = 1; i <= v; ++i)
        f[i] = inf;
    f[0] = 0;
     for(int i = 0; i < 2; ++i)
    {
        for(int j = S[i] ; j <= v; ++j)
        {
            f[j] = min(f[j], f[j - S[i]] + P[i]);
        }
    }
    int ret = inf;
    for(int i = need ;  i <= v ; ++i)
        ret = min(ret, f[i]);
    return ret;
}

bool judge(int data)
{
    int sum = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(data * x[i] - y[i] <= 0) continue;
        sum +=  cal(i, data, data * x[i] - y[i]);
        if(sum > s) return 1;
    }
    return 0;
}

int a[100005];
int main()
{
    while(scanf("%d %d",&n,&s) != EOF)
    {
        if(n == 0 && s == 0)break;
        int Min = inf;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d %d %d %d %d %d",&x[i],&y[i],&s1[i],&p1[i],&s2[i],&p2[i]);
            if((s1[i] * 1.0)/ p1[i] > (s2[i] * 1.0)/ p2[i])
            {
                int k = ((y[i] + (s * 1.0)/ p1[i] * s1[i]) * 1.0) / x[i] +5;
                if(k < Min) Min = k;
            }
            else{
                int k = ((y[i] + (s * 1.0)/ p2[i] * s2[i]) *1.0) / x[i] +5;
                if(k < Min) Min = k;
            }
        }
        int l = 0, r = Min;
        int mid ;
        while(l <= r)
        {
            mid = (l + r) >> 1;
            if(judge(mid))
                r = mid - 1;
            else
                l = mid + 1;
         }
        printf("%d\n",r);
     }
}