【问题描述】有n个重量分别为{w1,w2,…,wn}的物品,它们的价值分别为{v1,v2,…,vn},给定一个容量为W的背包。 设计从这些物品中选取一部分物品放入该背包的方案,每个物品要么选中要么不选中,要求选中的物品不仅能够放到背包中,而且满足重量限制(装入背包中物品重量和恰好为W ),并能具有最大的价值。
【提示】该问题的解空间是一棵子集树!
(1)对第i层上的某个分枝结点,对应的状态为dfs(i,tw,tv,op),其中tw表示装入背包中的物品总重量,tv表示背包中物品总价值,op记录一个解向量。该状态的两种扩展如下图所示:
(2)左剪枝:对于第i层的有些结点,如果tw+w[i]已超过了W,显然再选择w[i]是不合适的;
(3)右剪枝:rw=w[i]+w[i+1]+…+w[n], 当不选择物品i时:rw-w[i]=w[i+1]+…+w[n],若tw+rw-w[i]
参考代码为:
void dfs(int i,int tw,int tv,int rw,int op[])
{ //初始调用时rw为所有物品重量和
int j;
if (i>n) //找到一个叶子结点
{ if (tw==W && tv>maxv) //找到一个满足条件的更优解,保存
{ maxv=tv;
for (j=1;j<=n;j++) //复制最优解
x[j]=op[j];
}
}
else //尚未找完所有物品
{ if (tw+w[i]<=W) //左孩子结点剪枝
{ op[i]=1; //选取第i个物品
dfs(i+1,tw+w[i],tv+v[i],rw-w[i],op);
}
if ( tw+rw-w[i]>=W )
{ op[i]=0; //不选取第i个物品,回溯
dfs(i+1,tw,tv,rw-w[i],op);
}
}
}
【算法时间复杂度分析】
该算法不考虑剪枝时解空间树中有2n+1-1个结点(剪枝的结点个数不确定),所以最坏情况下算法的时间复杂度为O(2n)
【思考】如果要求:装入背包中物品重量和不超过W ,那么该如何剪枝?
源代码部分:
#include
using namespace std;
int n,W;
int maxv;//用于存放最优解对应的总价值
void dfs(int w[],int v[],int x[],int i,int tw,int tv,int op[],int rw){
if(i>n){ //找到一个叶子节点
if(tw==W && tv>maxv){
maxv=tv;
for(int j=1;j<=n;j++) x[j]=op[j];
}
}
else{
if(tw+w[i]<=W){
op[i]=1; //选取第i个物品
dfs(w,v,x,i+1,tw+w[i],tv+v[i],op,rw-w[i]);
}
if(tw+rw-w[i]>=W){ //直接减去w[i]是因为当前是讨论不选择该物品的情况
op[i]=0; //不选第i个物品 则回溯
dfs(w,v,x,i+1,tw,tv,op,rw-w[i]);
}
}
}
int main(){
while(cin>>n>>W){ //输入物品的数量
int w[n+1],v[n+1]; //分别用来存储物品的重量和价值 默认都不使用0下标
int x[n+1]; //用于存放最终解
maxv=0;int rw;//rw用于存储某个位置及其后续所有物品的价值总和
cout<<"please input the weight of n"<>w[i];rw+=w[i];} //rw存储所有物品重量的总和
cout<<"please input the value of n"<>v[j];
int tw=0,tv=0,op[n+1];
dfs(w,v,x,1,tw,tv,op,rw); //rw的初始值为所有物品的价值总和
cout<<"Result"<
运行结果部分:
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)