题面:
题意:
给 n(n<=1000) 个 A 班的人, m(m<=1000) 个 B 班的人,每个人都两个值 v(v<=1000),w(−1e9<=w<=1e9) ,你可以在 A ,B 班中各选一些人,使得 A 班中选出人的 v 之和等于 B 班中选出人的 v 之和并且最大化选出的人的 w 值之和。
题解:
我们把 A 班的同学的体积 v 看作正值,把 B 班同学的体积 v 看作负值,跑背包即可。
直接跑背包复杂度过高,会TLE。
(1)我们可以在跑背包时,可以只更新当前可达的状态,这样可以卡过去。
可以证明,这样对于 v 排个序的常数是最小的。
(2)随机打乱 n+m 个物品,可以认为最优解在某个阈值T上震荡,即只取 [−T,T]之间的状态即可。
代码(1):
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=1000100;
const int maxp=400100;
const int maxm=1100;
const int up=100;
ll dp[maxn];
pair<int,int>a[maxm],b[maxm];
int main(void)
{
int tt;
scanf("%d",&tt);
while(tt--)
{
int n,m;
scanf("%d%d",&n,&m);
int ansn=0,ansm=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].first,&a[i].second);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&b[i].first,&b[i].second);
ansm+=b[i].first;
b[i].first=-b[i].first;
}
sort(a+1,a+n+1);
sort(b+1,b+m+1);
memset(dp,0x80,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++)
{
ansn+=a[i].first;
for(int j=ansn;j>=a[i].first;j--)
dp[j]=max(dp[j],dp[j-a[i].first]+a[i].second);
}
for(int i=1;i<=m;i++)
{
for(int j=0;j<=ansm+b[i].first;j++)
dp[j]=max(dp[j],dp[j-b[i].first]+b[i].second);
ansm+=b[i].first;
}
printf("%lld\n",dp[0]);
}
return 0;
}
代码(2):
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=1000100;
const int maxp=400100;
const int maxm=2100;
const int up=200000;
ll dp[2][maxn];
pair<int,int>a[maxm];
int main(void)
{
int tt;
scanf("%d",&tt);
while(tt--)
{
srand(time(0));
int n,m;
scanf("%d%d",&n,&m);
int ansn=0,ansm=0;
for(int i=1;i<=n+m;i++)
{
scanf("%d%d",&a[i].first,&a[i].second);
if(i>n) a[i].first=-a[i].first;
}
//据说这个很随机。
for(int i=n+m;i>=1;i--)
{
swap(a[i],a[rand()%i+1]);
}
for(int i=0;i<=up;i++)
dp[0][i]=dp[1][i]=-lnf;
dp[0][up/2]=0;
bool flag=false;
for(int i=1;i<=n+m;i++)
{
flag^=1;
for(int j=0;j<=up;j++)
{
dp[flag][j]=dp[flag^1][j];
if(j-a[i].first>=0)
dp[flag][j]=max(dp[flag][j],dp[flag^1][j-a[i].first]+a[i].second);
}
}
printf("%lld\n",dp[flag][up/2]);
}
return 0;
}