《挑战程序设计竞赛》 超大背包问题实现

问题：有n个重量和价值分别为w[i]和v[i]的物品，从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和的最大值。

1 ≤ n ≤ 40

1 ≤ w[i], v[i] ≤ 10^15

1 ≤ W ≤ 10^15

分析：直接用01背包肯定超时。可以对前n/2个元素进行枚举sw1，然后后n-n/2个元素进行枚举sw,然后在sw1中二分查找<=W-sw的最大值。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <bitset>
#include <list>
#include <sstream>
#include <set>
#include <functional>
using namespace std;
#define maxn 41
#define inf 0x3f3f3f
#define esp 1e-10
typedef long long ll;
const ll INF = 1e18;

int n;
ll w[maxn],v[maxn];
ll W;
pair<ll,ll>ps[1 << maxn/2];

void solve(){
	//折半枚举
	int n2 = n/2;
	for (int i = 0; i < 1<<n2; ++i){
		ll sw = 0,sv = 0;
		for (int j = 0; j < n2; ++j)
			if(i>>j & 1) 
				sw += w[j],sv += v[j];
		ps[i] = make_pair(sw,sv);
	}

	//删掉不需要的状态
	sort(ps,ps+(1<<n2));
	int m = 0;//自己写往往是这样的，《挑战》里写的是m=1,m-1,m++,lower_bound(ps,ps+m)
	for (int i = 1; i < (1<<n2); ++i)
		if(ps[m].second < ps[i].second) 
			ps[++m] = ps[i];

	//二分查找
	ll ans = 0;
	for (int i = 0; i < 1<<(n-n2); ++i){
		ll sw = 0,sv = 0;
		for (int j = 0; j < n-n2; ++j)
			if(i>>j & 1) 
				sw += w[n2+j],sv += v[n2+j];
		if(sw <= W){
			ll tmp = (upper_bound(ps,ps+m+1,make_pair(W-sw,INF))-1)->second;
			//这个地方最好使用upper_bound
			//lower_bound使用<比较pair的first来确定返回结果，这和stl中的sort默认按照first来排序是一样的。
			//使用lower_bound的话，当找到的值正好等于W-sw时会漏掉，因此会出错。
			ans = max(ans,tmp+sv);
		}
	}
	printf("%lld\n", ans);
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d",&n);
	for (int i = 0; i < n; ++i) scanf("%lld%lld",&w[i],&v[i]);
	scanf("%lld",&W);
	solve();
	return 0;
}