首页 > 代码库 > 0-1背包-回溯法
0-1背包-回溯法
算法描述：
0-1背包的回溯法，与装载问题的回溯法十分相似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树进行搜索。否则将右子树剪去。
计算右子树上界的更好算法是：
将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。
算法实现：
由Bound函数计算当前节点处的上界。
类Knap的数据成员记录解空间树的节点信息，以减少参数传递及递归调用所需的栈空间。
在解空间树的当前扩展结点处，仅当要进入右子树时，才计算上界bound，以判断是否可将右子树剪去。
进入左子树时不需要计算上界，因为它与其父节点的上界相同。
算法实现：（代码有点小问题，正在修改中）
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
template <class Typew,class Typep>
class Knap{
friend Typep Knapsack(Typep *,Typew *,Typew,int);
private:
Typep Bound(int i);
void Backtrack(int i);
Typew c;//背包容量
int n;//物品数
Typew * w;//物品重量数组
Typep * p;//物品价值数组
Typew cw;//当前重量
Typep cp;//当前价值
Typep bestp;//当前最优价值
};
template <class Typew,class Typep>
void Knap<Typew,Typep>::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);
}
template <class Typew,class Typep>
Typep Knap<Typew,Typep>::Bound(int i)//计算上界
{
Typew cleft = c- cw;//剩余容量
Typep 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 Knapsack(int *,int *,int,int);
public:
int operator <= (Object a)const
{
return (d >= a.d);
}
private:
int ID;
float d;
};
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
template <class Typew,class Typep>
Typep Knapsack(Typep p[],Typew w[],Typew c,int n)
{
int i;
//初始化
int W = 0;
int P = 0;
Object* Q = new Object[n];
for(i=0;i<n;i++)
{
// cout<<p[i]<<" "<<w[i]<<endl<<"-------------------------"<<endl;
Q[i].ID = i;
Q[i].d = 1.0*p[i]/w[i];
// cout<<Q[i].ID<<" "<<Q[i].d<<endl<<"----------------------"<<endl;
P += p[i];
W += w[i];
// cout<<P<<" "<<W<<endl<<endl;
}
if(W<=c)
return P;//装入所有物品
//依物品单位重量价值排序
qsort (Q,n, sizeof(int), compare);
Knap<Typew,Typep> K;
K.p = new Typep [n+1];
K.w = new Typew [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.n = n;
K.bestp = 0;
K.Backtrack(1);
// cout<<K.bestp<<endl;
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
int main()
{
int p[4] = {9,10,7,4};
int w[4]= {3,5,2,1};
int num = Knapsack(p,w,7,4);
cout<<num<<endl;
return 0;
}
0-1背包-回溯法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。