该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
我用w[5]={2,2,6,5,4},p[5]={6,3,5,4,6}进行验证，最优值应该是15，可是输出结果是14
#include
#include
using namespace std;
class Knap
{
friend int Knaspack(int *,int *,int ,int );
public :
int Bound(int i);
void Backtrack(int i);
int c;//背包承载物品的数量
int n;//物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最有价值
};
void Knap::Backtrack(int i)
{
if(i>n)//到达叶子结点
{
bestp=cp;
return ;
}
if(cw+w[i]<=c)//搜素左子树
{
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子树
Backtrack(i+1);
}
int Knap::Bound(int i)//计算上界
{
int cleft=c-cw;//剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//装满物品
if(i<=n)
b+=p[i]*cleft/w[i];
return b;
}
class Object
{
friend int Knaspack(int *,int *,int ,int );
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
int ID;///物品编号
float d;//单位物品重量价值
};
int Knapsack(int p[],int w[],int c,int n)
{//初始化
int W=0;
int P=0;
Object * Q=new Object[n];
for(int i=1; i<=n; i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];/
W+=w[i];/
}
if(W<=c)//装入所有物品
return P;
//依照物品单位重量降序排序
float f;
for( i=1; i
for(int j=0; j
{
if(Q[j]<=Q[j+1])
{
f=Q[j].d;
Q[j].d=Q[j+1].d;
Q[j+1].d=f;
}
}
Knap K;
K.p=new int [n+1];
K.w=new int [n+1];
for( i=1; i<=n; i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
K.Backtrack(1);//从根开始搜索解空间树
delete[] Q;
delete[] K.w;
delete[] K.p;
return K.bestp;
}
int main()
{
int *p,*w,c,n;
int a[100];
int k=0;
while(cin>>n>>c && n+c)
{
w=new int [n+1];
for(int i=1; i<=n; i++)
cin>>w[i];
w[0]=0;
p=new int [n+1];
p[0]=0;
for( i=1; i<=n; i++)
cin>>p[i];
a[k]=Knapsack(p,w,c,n);
k++;
}
for(int i=0; i
{
cout<
}
return 0;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176719.html原文链接：https://javaforall.net
