算法设计与分析实验报告三
五.实验程序：
#include<iostream>
#include<stack>
#define N 200
using namespace std;
class HeapNode
{
public:
double uprofit,profit,weight;
int level,x[N];
};
stack<HeapNode> H;
double w[N],p[N];
double cw,cp,c;
int n;
double Bound(int i)
{
double cleft=c-cw,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 AddLiveNode(double up,double cp,double cw,bool ch,int level)
{
HeapNode nod;
nod.uprofit=up;
nod.profit=cp;
nod.weight=cw;
nod.level=level;
if(level<=n) H.push(nod);
}
double Knap()
{
int i=1;
cw=cp=0;
double bestp=0,up=Bound(1);
while(1)
{
double wt=cw+w[i];
if(wt<=c)
{
if(cp+p[i]>bestp) bestp=cp+p[i];
AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);
}
up=Bound(i+1);
if(up>=bestp)
AddLiveNode(up,cp,cw,false,i+1);
if(H.empty()) return bestp;
HeapNode node=H.top();
H.pop();
cw=node.weight;
cp=node.profit;
up=node.uprofit;
i=node.level;
}
}
int main()
{
cout<<"请输入n和c:"; cin>>n>>c;
cout<<"请输入w[i]"<<endl;
for(int i=1;i<=n;i++) cin>>w[i];
cout<<"请输入p[i]"<<endl;
for(int j=1;j<=n;j++) cin>>p[j];
cout<<"最优值是："<<Knap()<<endl;
return 0;
}
第二篇：实验四 回溯算法和分支限界法
实验四 回溯算法和分支限界法
0-1背包问题
一、实验目的
:
1、掌握0-1背包问题的回溯算法；
2、进一步掌握回溯算法。
二、实验内容
给定n和物品和一人背包，物品i的重量是wi，其价值为vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？
三、实验步骤
1、代码
// HS_ALG.cpp : Defines the entry point for the console application.
//
#include<iostream>
#include<algorithm>
using namespace std;
// 物体结构体
typedef struct{
float w; //物品重量
float p; //物品价值
float v; //背包体积
int id; //物品个数
}OBJECT;
bool cmp(OBJECT a, OBJECT b){ //比较两物品体积
return a.v>b.v;
}
float knapsack_back(OBJECT ob[], float M, int n, bool x[]){ //回溯法
int i,k;
float w_cur, p_total, p_cur, w_est, p_est;
bool *y = new bool[n+1];
// 计算物体的价值重量比
for(i=0; i<=n; i++){
ob[i].v = ob[i].p/ob[i].w;
y[i] = false;
}
// 按照物体的价值重量比降序排列
sort(ob, ob+n, cmp);
// 初始化当前背包中的价值、重量
w_cur = p_cur = p_total = 0;
// 已搜索的可能解的总价值初始化
k = 0;
while(k>=0){
w_est = w_cur; p_est = p_cur;
// 沿当前分支可能取得的最大价值
for( i=k; i<n; i++) {
w_est += ob[i].w;
if(w_est<M){
p_est += ob[i].p;
}else{
p_est += ((M-w_est+ob[i].w)/ob[i].w)*ob[i].p;
break;
}
}
// 估计值大于上界
if(p_est>p_total){
for(i=k; i<n; i++){
if(w_cur+ob[i].w<=M){
// 可装入第i个物体
w_cur = w_cur + ob[i].w;
p_cur = p_cur + ob[i].p;
y[i] = true;
}else{
// 不能装入第i个物体
y[i] = false;
break;
}
}
if(i>=n){
// n个物体已经全部装入
if(p_cur>p_total){
// 更新当前上限
p_total = p_cur;
k = n;
// 保存可能的解
for(i=0; i<n; i++){
x[i] = y[i];
}
}
}else{
// 继续装入物体
k = i+1;
}
}else{
// 估计值小于上界时
while((i>=0)&&(!y[i]))i--; // 沿着右分支结点方向回溯直到左分支结点
if(i<0)break; // 到达根结点 算法结束
else{ // 修改当前值
w_cur -= ob[i].w;
p_cur -= ob[i].p;
y[i] = false;
k = i+1; // 搜索右分支子树
}
}
}
//delete y;
return p_total;
}
int main(){
int n;
float m;
cout<<"请输入背包载重：";
cin>>m;
cout<<"请输入物品个数：";
cin>>n;
OBJECT* ob = new OBJECT[n];
{
cout<<"请输入物品的重量、价格："<<endl;
for(int i=0; i<n; i++){
cin>>ob[i].w>>ob[i].p;
ob[i].id = i+1;
}
}
bool* x = new bool[n];
float v = knapsack_back(ob, m, n, x);
{
cout<<"最优方案："<<endl;
for(int i=0; i<n; i++){
if(x[i])cout<<"["<<ob[i].id<<"] ";
}
cout<<endl;
cout<<"物品总价值为："<<v<<endl;
}
return 0;
}
2、结果
执行成功.
3、结果分析