1514: Packs
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 61 Solved: 4
[Submit][Status][Web Board]
Description
Give
you n packs, each of it has a value v and a weight w. Now you should
find some packs, and the total of these value is max, total of these
weight is equal to m.
Input
First line is a number T( T ≤ 5) represent the test cases.
Then for each set of cases, first line is n (1 ≤ n ≤ 40) and m (1 ≤ m
< 2^31), follow n line each is Wi (1 ≤ Wi < 2^31) and Vi (-2^31
< Vi < 2^31).
Output
Each case a line for max value.(Each set of inputs to ensure the solvability)
Sample Input
2
3 3
1 1
2 2
3 4
5 2
1 -5
1 -8
1 0
1 -2
1 5
Sample Output
4
5 注意：这里要求是满足总重量必须固定，而不是接近总重量。这就成了直接折半枚举，map大法就行了。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long LL;
const long long INF=99999999999999999LL;
const int EXP=1e-;
const int MS=; map<LL,LL> mp;
int n;
LL W; LL w[MS],v[MS]; void solve()
{
mp.clear();
int n1=n/;
for(int i=;i<(<<n1);i++)
{
LL sw=,sv=;
for(int j=;j<n1;j++)
{
if((i>>j)&)
{
sw+=w[j];
sv+=v[j];
}
}
mp[sw]=max(mp[sw],sv);
}
LL ans=-INF;
for(int i=;i< <<(n-n1);i++)
{
LL sw=,sv=;
for(int j=;j<(n-n1);j++)
{
if((i>>j)&)
{
sw+=w[n1+j];
sv+=v[n1+j];
}
}
if(mp.count(W-sw))
ans=max(ans,mp[W-sw]+sv);
}
printf("%lld\n",ans);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%lld",&n,&W);
for(int i=;i<n;i++)
scanf("%lld%lld",&w[i],&v[i]);
solve();
}
return ;
}
如果是重量不大于 W ，那么就要折半枚举+二分查找。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF=0x4fffffff;
const int EXP=1e-;
const int MS=; int n;
LL W;
LL w[MS],v[MS];
struct node
{
LL w,v;
bool operator <(const node &a) const //注意一定要加上const
{
return w<a.w||(w==a.w&&v<a.v);
}
}nodes[<<(MS/)]; LL find(LL w,int cnt)
{
int l=,r=cnt;
while(r-l>) // 左闭右开区间处理起来更方便。
{
int mid=(l+r)/;
if(nodes[mid].w<=w)
l=mid;
else
r=mid;
}
return nodes[l].v;
} void solve()
{
int n1=n/;
int cnt=;
for(int i=;i<(<<n1);i++)
{
LL sw=,sv=;
for(int j=;j<n1;j++)
{
if((i>>j)&)
{
sw+=w[j];
sv+=v[j];
}
}
nodes[cnt].w=sw;
nodes[cnt++].v=sv;
}
sort(nodes,nodes+cnt);
int last=;
for(int i=;i<cnt;i++)
{
if(nodes[last].v<nodes[i].v)
{
nodes[++last]=nodes[i];
}
}
cnt=last+;
LL ans=;
for(int i=;i< <<(n-n1);i++)
{
LL sw=,sv=;
for(int j=;j<(n-n1);j++)
{
if((i>>j)&)
{
sw+=w[n1+j];
sv+=v[n1+j];
}
}
if(sw<=W)
{
LL tv=find(W-sw,cnt);
ans=max(ans,sv+tv);
}
}
printf("%lld\n",ans);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%lld",&n,&W);
for(int i=;i<n;i++)
scanf("%lld%lld",&w[i],&v[i]);
solve();
}
return ;
}