Description
【题目描述】
蛤布斯有n个物品和一个大小为m的背包，每个物品有大小和价值，它希望你帮它求出背包里最多能放下多少价值的物品。
【输入数据】
第一行两个整数n,m。接下来n行每行两个整数xi，wi，表示第i个物品的大小和价值。
【输出数据】
一行一个整数表示最大价值。
【样例输入】
5 100
95 80
4 18
3 11
99 100
2 10
【样例输出】
101
【数据范围】
对于20%的数据，xi<=1500。
对于另外30%的数据，wi<=1500。
对于100%的数据，n<=40,0<=m<=10^18,0<=xi,wi<=10^15。
中途相遇法这个东西比较有意思.
这题接近于可行的办法就是暴搜, O(2 ^ n), 但是会炸掉.
不难发现, 假如时间复杂度优化至O(2 ^ (n / 2)), 那么这题就是可以过的, 因此可以这样做:
把所有物品分为左右两半, 2 ^ (n / 2)枚举在同一半中每一种选取物品方案(即从小到大枚举i)所得到的价值以及, 记录入L[i], R[i]中(通过i的二进制拆分来得到当前的具体方案).
将L, R排序, 去掉那些空间大而价值小的方案, 扫一遍利用决策单调性即可得到答案.
附上代码(跑得好慢…)
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxN = 40;
struct item
{
long long size, val;
item(){}
item(long long first, long long second): size(first), val(second){}
}a[maxN], L[1 << (maxN >> 1)], R[1 << (maxN >> 1)];
int operator <(item x, item y)
{
if(x.size == y.size)
return x.val > y.val;
return x.size < y.size;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("pack.in", "r", stdin);
freopen("pack.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
long long n, m;
cin >> n >> m;
for(int i = 0; i < n; i ++)
cin >> a[i].size >> a[i].val;
int mid = n >> 1;
for(int i = 0; i < 1 << (mid); i ++)
{
long long sizeSum = 0, valSum = 0;
for(int j = 0; j < mid; j ++)
if((i >> j) & 1)
sizeSum += a[j].size, valSum += a[j].val;
L[i] = item(sizeSum, valSum);
}
sort(L, L + (1 << mid));
long long cntL = 1;
for(int i = 1; i < 1 << mid; i ++)
if(L[cntL - 1].val < L[i].val)
L[cntL ++] = L[i];
for(int i = 0; i < 1 << (n - mid); i ++)
{
long long sizeSum = 0, valSum = 0;
for(int j = 0; j < n - mid; j ++)
if((i >> j) & 1)
sizeSum += a[mid + j].size, valSum += a[mid + j].val;
R[i] = item(sizeSum, valSum);
}
sort(R, R + (1 << (n - mid)));
long long cntR = 1;
for(int i = 1; i < 1 << (n - mid); i ++)
if(R[cntR - 1].val < R[i].val)
R[cntR ++] = R[i];
long long p = 0, q = cntR - 1;
long long ans = 0;
for(int p = 0; p < cntL; p ++)
{
while(L[p].size + R[q].size > m && q)
q --;
if(L[p].size + R[q].size > m)
continue;
ans = max(ans, L[p].val + R[q].val);
}
cout << ans;
}