《算法设计与分析》实验报告八
一、实验内容：
分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。
二、所用算法的基本思想及复杂度分析：
1、 蛮力法
1） 基本思想
用蛮力法求解就是要穷举出物品的所有组合，计算不超过背包容量的物品的最大价值和
2） 复杂度分析
装法有2n种组合，每种组合中又要计算价值和，所以其复杂度为指数级。
2、 动态规划法
1） 基本思想
动态规划法的关键在于找到决策函数，在本例中，令V(i,j)表示在前i个物品中能够装入容量为j的背包中的物品的最大值,则有如下动态规划函数：
V(i,0)=V(0,j)=0; (1)
V(i-1,j) j<wi
V(i,j)= (2)
max{V(i-1,j),V(i-1,j-wi)+vi} j>=wi
式(1)表明：把前面i个物品的装入容量为0的背包和把0个物品装入容量为j的背包，得到的总价值都是0。式(2)的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：1.如果把第i个物品装入背包，则背包中的物品价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；2.如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然取二者的较大值作为把前i个物品装入容量为j的背包中的最优解。
2） 复杂度分析
时间复杂度是O(n*c)。
3、 回溯法
1） 基本思想
回溯法是一种有组织的系统化搜索技术，可以看作是蛮力法穷举搜索的一种改进。具体在0/1背包问题中的使用如下：
回溯法从0/1背包问题的解空间树的根节点出发，按照深度优先遍历解空间树，搜索满足约束条件的解。在搜索到树中的任一结点时，先判断该结点的对应部分的解是否满足约束条件，或者是否超出目标函数的界,也就是判断该结点是否包含问题的(最优)解，如果不包含则跳过对以该结点为根的子树的搜索；否则进入以该结点为根的子树继续深度优先遍历搜索。
2） 复杂度分析
0/1背包问题的解空间树是一棵子集树，遍历一棵子集树所需时间为Ω(2n)。
4、 分支限界法
1） 基本思想
分支限界法按照广度优先法遍历整个解空间树，在遍历过程中，对已经处理过的每一个结点根据限界函数估算目标函数的可能值，从中选取使目标函数取得极大或极小的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的最优解。
2） 复杂度分析
由于分治限界法是蛮力法的一种改进，所以在0/1背包问题中，问题的复杂度在最坏的情况下是指数阶的。
三、源程序及注释：
#define MAX 100
#define max(a,b) (a>b)?a:b
#include <MATH.H>
#include <VECTOR>
#include <stdio.h>
#include <stdlib.h>
#include <WINDOWS.H>
#include <TIME.H>
#include <IOSTREAM>
#include <algorithm>
using namespace std;
//设计物品属性，重量和价值
typedef struct{
double w; //重量
double v; //价值
}OBJECT;
//回溯法
int bestV=0; //最大价值
int cw=0; //当前重量
int cv=0; //当前价值
//进入右子树条件
int R_Bentch(int i,int n,int c,OBJECT t[])
{
int j=i;
int left_C=c-cw;
int tempV=cv;
while(t[j].w<left_C&&j<n)
{
left_C-=t[j].w;
tempV+=t[j].v;
j++;
}
return tempV;
}
//递归
void BackTrack(int i,int n,int c,OBJECT t[])
{
if (i>=n)
{
if(bestV<cv)
bestV=cv;
return;
}
if(cw+t[i].w<=c) //进入左子树
{
cw+=t[i].w;
cv+=t[i].v;
BackTrack(i+1,n,c,t);
cw-=t[i].w; //回溯前回复到上一状态
cv-=t[i].v;
}
if(R_Bentch(i+1,n,c,t)>bestV) //进入右子树
BackTrack(i+1,n,c,t);
}
//分支限界-----------------------------------------
//状态结构体
typedef struct{
bool s1[MAX]; //当前放入物体
int k; //搜索深度
double b; //价值上界
double w; //物体重量
double v; //物体价值
}KNAPNODE;
//堆元素结构体
typedef struct {
KNAPNODE *p; //结点数据
double b; //所指结点的上界
}HEAP;
//比较两个物体价值比
int cmp(OBJECT a,OBJECT b)
{
return a.v/a.w>b.v/b.w;
}
//交换两个堆元素
void swap(HEAP &a,HEAP &b)
{
HEAP temp=a;
a=b;
b=temp;
}
//堆中元素上移
void sift_up(HEAP H[],int i)
{
bool done=false;
if(i!=1)
{
while(!done&&i!=1)
{
if(H[i].b>H[i/2].b)
swap(H[i],H[i/2]);
else
done=true;
i=i/2;
}
}
}
//堆中元素下移
void sift_down(HEAP H[],int n,int i)
{
bool done=false;
if((2*i)<=n)
{
while(!done&&((i=2*i)<=n))
{
if(i+1<=n&&H[i+1].b>H[i].b)
i++;
if(H[i/2].b<H[i].b)
swap(H[i/2],H[i]);
else
done=true;
}
}
}
//往堆中插入结点
void insert(HEAP H[],HEAP x,int &n)
{
n++;
H[n]=x;
sift_up(H,n);
}
//删除堆中的结点
void del(HEAP H[],int &n,int i)
{
HEAP x,y;
x=H[i];
y=H[n];
n--;
if(i<=n)
{
H[i]=y;
if(y.b>=x.b)
sift_up(H,i);
else
sift_down(H,n,i);
}
}
//获得堆顶元素并删除
HEAP delete_max(HEAP H[],int &n)
{
HEAP x=H[1];
del(H,n,1);
return x;
}
//计算分支结点的上界
void bound(KNAPNODE* node,double M,OBJECT ob[],int n)
{
int i=node->k;
double w=node->w;
double v=node->v;
if(node->w>M)
{ //物体重量超过背包的容量
node->b=0; //上界置为0
}
else
{
while((w+ob[i].w<=M)&&(i<n))
{
w+=ob[i].w; //计算背包已载入载重
v+=ob[i++].v; //计算背包已装入价值
}
if(i<n)
node->b=v+(M-w)*ob[i].v/ob[i].w;
else
node->b=v;
}
}
//分支限界求解函数
//输入：n个物体的重量和价值数组ob[]，背包载重M
//输出：装入背包的物体最优价值v
double knapsack_bound(OBJECT ob[],double M,int n)
{
int i,k=0; //堆中元素个数计数器初始化为0
double v;
KNAPNODE *xnode,*ynode,*znode;
HEAP x,y,z,*heap;
heap=new HEAP[n*n]; //分配堆的存储空间
sort(ob,ob+n,cmp); //对物体按照价值重量比排序
xnode=new KNAPNODE; //建立父结点
for(i=0;i<n;i++) //初始化结点
xnode->s1[i]=false;
xnode->k=xnode->w=xnode->v=0;
while (xnode->k<n)
{
ynode=new KNAPNODE; //建立y结点
*ynode=*xnode; //结点x的数据复制到y
ynode->s1[ynode->k]=true; //装入第k个物体
ynode->w+=ob[ynode->k].w; //背包中物体的累计重量
ynode->v+=ob[ynode->k].v; //背包中物体的累计价值
ynode->k++; //搜索深度++
bound(ynode,M,ob,n); //计算结点y的上界
y.b=ynode->b;
y.p=ynode;
insert(heap,y,k); //结点y按上界的值插入到堆中
znode=new KNAPNODE; //建立结点z
*znode=*xnode; //结点x数据复制到z
znode->k++; //搜索深度++
bound(znode,M,ob,n); //计算结点z的上界
z.b=znode->b;
z.p=znode;
insert(heap,z,k); //结点z按上界的值插入堆中
delete xnode;
x=delete_max(heap,k); //获得堆顶元素作为新的父亲结点
xnode=x.p;
}
v=xnode->b;
delete xnode;
delete heap;
return v; //返回背包中物体的价值
}
//动态规划---------------------------------------
double KnapSack(int n,int c,OBJECT ob[])
{
int i,j;
vector<vector<double> > V(n+1, vector<double>(c+1));
for(i=0;i<=n;i++)
V[i][0]=0;
for(j=0;j<=c;j++)
V[0][j]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=c;j++)
{
if(j<ob[i].w)
V[i][j]=V[i-1][j];
else
V[i][j]=max(V[i-1][j],V[i-1][j-ob[i].w]+ob[i].v);
/* cout<<V[i][j]<<" ";*/
}
/* cout<<endl;*/
}
return V[n][c];
}
//蛮力法---------------------------------------
void conversion(int n,int b[MAX])//将n化为二进制形式，结果存放到数组b中
{
int i;
for(i=0;i<MAX;i++)
{
b[i] = n%2;
n = n/2;
if(n==0)break;
}
}
double Force(int n,int c,OBJECT ob[])
{
int i,j;
int b[MAX];
double maxv;
double temp_v,temp_w;
maxv = 0;
//分别求出所有的子集，按要求寻找最大的子集
for (i=0;i<pow(2,n);i++)
{
for (j=0;j<n;j++)
{
b[j] = 0;
}
conversion(i,b);
temp_v = 0;
temp_w = 0;
for (j=0;j<n;j++)
{
if (b[j]==1)
{
temp_w = temp_w+ob[j].w;
temp_v = temp_v+ob[j].v;
}
}
if ((temp_w<=c)&&(temp_v>=maxv))
maxv = temp_v;
}
return maxv;
}
//主函数===============================================
void main()
{
OBJECT t[MAX];
int n; //实际物品数
int c; //背包容量
int i;
//测时间
LARGE_INTEGER begin,end,frequency;
QueryPerformanceFrequency(&frequency);
//输入
cout<<"输入物品总数:";
cin>>n;
cout<<"输入背包的总容量:";
cin>>c;
srand(time(0));
for (i=0;i<n;i++)
{
t[i].w=rand()%11+rand()%17;
t[i].v=rand()%37+rand()%61;
cout<<"第"<<i+1<<"个物品重量:"<<t[i].w
<<" 价值:"<<t[i].v<<endl;
}
//分支限界-----------------------------------------------------
double maxV;
QueryPerformanceCounter(&begin);
maxV=knapsack_bound(t,c,n);
QueryPerformanceCounter(&end);
cout<<"**************分支限界法********************"<<endl;
cout<<"结果:"<<maxV<<endl;
cout<<"时间:"
<<(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart
<<"s"<<endl;
//动态规划-----------------------------------------------------
QueryPerformanceCounter(&begin);
maxV=KnapSack(n,c,t);
QueryPerformanceCounter(&end);
cout<<"**************动态规划法********************"<<endl;
cout<<"结果:"<<maxV<<endl;
cout<<"时间:"
<<(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart
<<"s"<<endl;
//蛮力法-------------------------------------------------------
QueryPerformanceCounter(&begin);
maxV=Force(n,c,t);
QueryPerformanceCounter(&end);
cout<<"****************蛮力法**********************"<<endl;
cout<<"结果:"<<maxV<<endl;
cout<<"时间:"
<<(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart
<<"s"<<endl;
//回溯法------------------------------------------------------
QueryPerformanceCounter(&begin);
sort(t,t+n,cmp);
BackTrack(0,n,c,t);
QueryPerformanceCounter(&end);
cout<<"****************回溯法**********************"<<endl;
cout<<"结果:"<<bestV<<endl;
cout<<"时间:"
<<(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart
<<"s"<<endl;
}
四、运行输出结果：
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
该实验用四种方法求解0-1背包问题，蛮力法，回溯法，分支限界法的复杂度都是指数级，动态规划法结果错误，分支限界方法是从网上找的。