ZOJ 3631 超大背包 + 折半搜索

发表于 | 分类于 | 阅读次数：

将$2^k$种状态分开进行折半搜索，我怎么就想不到？

题目链接

题意

教练有一些钱，你也有一些钱，告诉你每天必须花费的钱数，你在一天当中要么只花自己的钱，要么只花教练的钱，问你最多能花教练多少钱。

思路

实际上对于每天都有花和不花两种状态，这样的话就是$2^{30}$种状态，肯定不行，我们可以先枚举前一半的状态，存一下然后排序，然后枚举后一半状态的时候，对前一半的状态进行折半搜索。

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
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define Close ios::sync_with_stdio(false);
#define Debug cout << "-----------------" << '\n';
ll c[1 <<(15)];

ll a[31];
int tot ;
int main()
{
    ll n, m;
    while(scanf("%lld %lld",&n,&m) != EOF){
    tot = 0;
    for(int i = 0; i < n; ++i)
    {
        scanf("%lld",&a[i]);
    }
    int mid = n / 2;
    for(int i = 0; i < (1 << mid); ++i)
    {
        ll sum = 0;
        for(int j = 0; j < mid; ++j)
        {
            if((i >> j) & 1)
            {
                sum += a[j];
            }
        }
        c[++tot] = sum;
    }
    sort(c + 1,c + tot + 1);
    ll Max = -1;
    for(int i = 0; i < (1 << (n - mid)); ++i)
    {
        ll sum = 0;
      //  cout <<"i: " << i << '\n';
        for(int j = 0; j < n - mid; ++j)
        {
       //     cout << "j: " << j << '\n';
            if((i >> j) & 1)
            {
                sum += a[j + mid];
            }
        }
        if(sum <= m){
        int M = lower_bound(c + 1, c + tot + 1, m - sum) - c;
        if(c[M] + sum == m) Max = max(Max, c[M] + sum);
        if(c[M] + sum > m || M == tot + 1)
        {
            if(c[M - 1] + sum <= m)
                Max = max(Max, c[M - 1] + sum);
        }
         Max = max(Max, sum);
        }
    }
    cout << Max << '\n';
    }
}