01背包问题变形
程序员文章站
2022-06-06 17:50:52
...
一、问题
二、解题思路
三、c++代码
下面是我自己理解写的,没有根据标准答案的,那答案在讲啥?。。一直没法AC,,不过还是可以解决问题的。n件物品按单位重量价值降序排序,然后回溯法装,右结点必要时剪枝,刚好凑成重量为m的若干件物品才能得到一个解。
#include<iostream>
#define MAX 50
using namespace std;
int n,m;
double cw,cp,bestp,perp[MAX],w[MAX],v[MAX];
void swap(int i,int j)
{
double t;
t=perp[i];perp[i]=perp[j];perp[j]=t;
t=w[i];w[i]=w[j];w[j]=t;
t=v[i];v[i]=v[j];v[j]=t;
}
void quicksort(int p,int q)
{
int i=p,j=q;
double key=perp[p];
if(p>=q)
{
return;
}
while(1)
{
while(j>=p && perp[j]<key)
j--;
if(j<=i)
break;
swap(i,j);
while(i<=q && perp[i]>=key)
i++;
if(j<=i)
break;
swap(i,j);
}
quicksort(p,j-1);
quicksort(j+1,q);
}
double bound(int i)
{
if(i>n) return cp;
double leftw= m-cw;
double b =cp;
while(i<=n&&w[i]<=leftw)
{
leftw-=w[i];
b+=v[i];
i++;
}
if(i<=n)
b+=perp[i]*leftw;
return b;
}
void backtrack(int i)
{
if(i>n)
{
if(cw==m && cp>bestp)
{
bestp = cp;
}
return ;
}
if(cw+w[i]<=m)
{
cw+=w[i];
cp+=v[i];
backtrack(i+1);
cw-=w[i];
cp-=v[i];
}
if(bound(i+1)>bestp)
backtrack(i+1);
}
void pack()
{
int i,j;
for(i=1; i<=n; i++)
{
perp[i]=v[i]/w[i];
}
quicksort(1,n);
backtrack(1);
}
int main()
{
int T,i,a=0;
double ans[MAX];
cin >> T;
while(T>0)
{
bestp=0.0;
cw=0.0;
cp=0.0;
cin >> n >> m;
for(i=1; i<=n; i++)
{
cin >> w[i] >> v[i];
}
pack();
ans[a++]=bestp;
T--;
}
for(i=0; i<a; i++)
{
cout << ans[i] <<endl;
}
system("pause");
return 0;
}
看了一位大神的答案。。。
原文:http://www.cnblogs.com/767355675hutaishi/p/4388362.html
原来要用折半枚举+二分查找:
#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-5;
const int MS=42;
map<LL,LL> mp;
int n;
LL W;
LL w[MS],v[MS];
void solve()
{
mp.clear();
int n1=n/2;
for(int i=0;i<(1<<n1);i++)
{
LL sw=0,sv=0;
for(int j=0;j<n1;j++)
{
if((i>>j)&1)
{
sw+=w[j];
sv+=v[j];
}
}
mp[sw]=max(mp[sw],sv);
}
LL ans=-INF;
for(int i=0;i< 1<<(n-n1);i++)
{
LL sw=0,sv=0;
for(int j=0;j<(n-n1);j++)
{
if((i>>j)&1)
{
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=0;i<n;i++)
scanf("%lld%lld",&w[i],&v[i]);
solve();
}
return 0;
}
我决定还是回去好好修炼。。
上一篇: 如何避免oracle全表扫描
下一篇: PHP程序中的常见漏洞详解_PHP教程