算法设计与分析实验报告资料

设所给0-1背包问题的子问题

的最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质,可以建立计算m(i,j)的递归式:

注:(3.4.3)式此时背包容量为j,可选择物品为i。此时在对xi作出决策之后,问题处于两种状态之一:

(1)背包剩余容量是j,没产生任何效益; (2)剩余容量j-wi,效益值增长了vi ;

1.3算法描述

int m[100][100];//前i个物品装入容量为j的背包中获得的最大价值 int s;//获得的最大价值 int w[15];//物品的重量 int v[15];//物品的价值

int x[15];//物品的选取状态,1表示被选中 0表示未选中 int n,i;

int c;//背包最大容量

int max(int a,int b)//获得最大值 int min(int a,int b)//获得最小值

void KnapSack(int n,int w[],int v[],int c)//背包问题主算法

先为m[n][j] 初始化初值然后根据递归方程式进行穷举递归直到 m[1][c], m[1][c] 即为所获得的最大价值。

void Traceback(int n,int w[],int x[],int c)//回溯算法,依次标注被选中的物品

通过一个循环过程检验装入第i个物品与装入i+1个物品的价值如果相同,则x[i]=0。

1.4程序实现及程序截图 1.4.1程序源码

#include using namespace std;

int m[100][100];//前i个物品装入容量为j的背包中获得的最大价值 int max(int a,int b)

4 {

if(a>=b) return a; else return b; }

int min(int a,int b) {

if(a>=b) return b; else return a; }

void KnapSack(int n,int w[],int v[],int c) { int i,j;

int jMax=min(w[n]-1,c); for(j=0;j<=jMax;j++) m[n][j]=0; for(j=w[n];j<=c;j++) m[n][j]=v[n]; for(i=n-1;i>1;i--) {

jMax=min(w[i]-1,c);

for(j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(j=w[i];j

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); }

m[1][c]=m[2][c]; if(c>=w[1])

m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); }

void Traceback(int n,int w[],int x[],int c) { int i;

for(i=1;i

if(m[i][c]==m[i+1][c]) x[i]=0; else{x[i]=1;c-=w[i];} x[n]=(m[n][c])?1:0; } int main()

1.4.2程序截图

{

int s;//获得的最大价值 int w[15];//物品的重量 int v[15];//物品的价值 int x[15];//物品的选取状态 int n,i;

int c;//背包最大容量

cout <<\请输入背包的最大容量:\ cin>>c;

cout<<\输入物品数:\\n\ cin>>n;

cout<<\请分别输入物品的重量:\ for(i=1;i<=n;i++) cin>>w[i];

cout<<\请分别输入物品的价值:\ for(i=1;i<=n;i++) cin>>v[i];

KnapSack(n,w,v,c); Traceback(n,w,x,c); s=m[1][c];

cout<<\最大物品价值为:\ cout<

cout<<\选中的物品为:\ for(i=1;i<=n;i++) cout<

return 0;

5

1.5学习或程序调试心得

利用动态规划求解0-1背包问题的复杂度为0(min{nc,2n}。动态规划主要是求解最优决策序列,当最优决策序列中包含最优决策子序列时,可建立动态规划递归方程,它可以帮助高效地解决问题。

6

作业2 0-1背包问题的回溯算法

1.1算法应用背景

背包问题是一个在运筹学领域里常见的典型NP-C难题,也是算法设计分析中的经典问题,对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法,对该问题的探索和应用研究一直在进行。在先进理论指导下,求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。

那么要解决背包问题,首要的前提就是设计出好的算法,想求得背包问题的解,就要先设计出算法,本文采用回溯法对背包问题给出具体算法设计和实现过程。如何将背包问题应用于实际问题中,有针对性地设计适合求解实际0-1背包问题的算法,并很好地解决实际问题,是计算机工作者不断思索、研究的一个领域。

2.2算法原理 2.2.1 问题描述

问题的一般描述是:旅行者背包登山,背包的最大承重为M,现有n个物品可供选择装入背包,第i个物品莺量为wi,价值为pi,假定物品i的一部分xi(0?xi?1)放人背包,获得价值为xipi,由于背包最大承重为M,要求装入物品总质量不过超过M,问旅行者应该如何选择物品装入背包,使得装入物品的价值总和达到最大值。

背包问题的数学描述如下:要求找到一个n元向量(x1,x2…xn),在满足约束条件:

???xiwi?M情况下,使得目标函数max?xi??0?x?1i?p,其中,1?i?n;M>0;wi>0;pi>0。

i满足约束条件的任何向量都是一个可行解,而使得目标函数达到最大的那个可行解则为最优

解。

给定n 种物品和1个背包。物品i 的重量是wi,其价值为pi,背包的容量为M。问应如何装入背包中的物品,使得装人背包中物品的总价值最大?在选择装人背包的物品时,对每种物品i只有两种选择,即装入背包、不装入背包。不能将物品i 装人背包多次,也不能只装入部分的物品i。该问题称为0-1背包问题。

0-1背包问题的符号化表示是,给定M>0, w i >0, pi >0,1?i?n ,要求找到一个n元0-1向量向量(x1,x2…xn), X i =0 或1 , 1?i?n, 使得

?xwii?M ,而且?xip达到最大。

i2.2.2算法分析

1、问题的解空间:应用回溯法解问题时,首先应明确定义问题的解空间。问题的解空间应

7

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4