当前位置:首页 >> 计算机软件及应用 >>

回溯法-0-1背包问题


源代码:
1.不带剪枝函数,非常类似装载问题
#include<iostream>
#include<algorithm>
using namespace std;
class Knapsack{
public:
Knapsack(double *pp,double *ww,int nn,double cc){
p = pp;
w = ww;
n = nn;
c = cc;
cw = 0;
cp = 0;
bestp = 0;
x = new int[n];
cx = new int[n];
}

void knapsack(){
backtrack(0);
}

void backtrack(int i){//回溯法
if(i > n){
if(cp > bestp){
bestp = cp;
for(int i = 0; i < n; i++)
x[i] = cx[i];
}
return;
}

if(cw + w[i] <= c){//搜索右子树
cw += w[i];
cp += p[i];
cx[i] = 1;
backtrack(i+1);
cw -= w[i];
cp -= p[i];
}
cx[i] = 0;
backtrack(i+1);//搜索左子树
}

void printResult(){
cout << "可以装入的最大价值为:" << bestp << endl;
cout << "装入的物品依次为:";
for(int i = 0; i < n; i++){
if(x[i] == 1)
cout << i+1 << " ";
}
cout << endl;
}

private:
double *p,*w;
int n;
double c;
double bestp,cp,cw;//最大价值,当前价值,当前重量
int *x,*cx;
};

int main(){
  double p[4] = {9,10,7,4},w[4] = {3,5,2,1};
Knapsack ks = Knapsack(p,w,4,7);
ks.knapsack();
  ks.printResult();
  return 0;
}
2.带剪枝函数的递归回溯(待看)
#include<iostream>
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//背包容量
int n; //物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最优值
int *bestx;//当前最优解
int *x;//当前解
};

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]/w[i]*cleft;
return b;
}

void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子树
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子树
{
x[i]=0;
Backtrack(i+1);
}
}

class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int ID;
float d;
};

int Knapsack(int p[],int w[],int c,int n)
{
//为Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(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=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}

}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
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);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int a[] ={0,9,10,7,4};
int b[] ={0,3,5,2,1};
int c=7;
int n=4;
int i=0;
int *p=a;
int *w=b;

cout<<"最优解为(bestx):"<<endl;
cout<<"最优值为(bestp):"<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
}

相关文章:
回溯算法解决0-1背包问题
回溯算法解决0-1背包问题 - 《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称:回溯算法....
用回溯法解决0-1背包问题
标签: 回溯法| 背包| 用回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决0-1背包问题 #include&lt;stdio.h&gt; int c; //背包容量 ...
回溯法解0-1背包问题实验报告
实验4 一 、实验要求 回溯法0-1 背包问题 1.要求用回溯法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。 ...
回溯法-0-1背包问题
回溯法-0-1背包问题 - 1、 问题描述 一、0-1 背包问题 给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,如何选择才能使 得物品的总价格最高...
0-1背包问题的解决(回溯法)
回溯法| 背包| 0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法和动态规划的方法解决0-1背包问题。 前面...
回溯算法解决0-1背包问题(DOC)
回溯算法解决0-1背包问题(DOC) - 《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称...
0-1背包问题(回溯法)
0-1背包问题(回溯法) - 0-1 背包问题(回溯法) 实验报告 姓 名: 学 号: 指导老师: 一.算法设计名称: 0-1 背包问题(回溯法) 二.实验内容 问题描述: ...
回溯法实验0 1背包问题 C++
回溯法实验0 1背包问题 C++ - #include &lt;iostream.h&gt; #include&lt;iomanip.h&gt; #include&lt;string.h&gt; int min(int w,int...
回溯法和分支限界法解决0-1背包题
0-1 背包问题计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一个(最...
回溯法和分支限界法解决0-1背包题(精)
0-1 背包问题 计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一 个(...
更多相关标签: