目录
一、问题描述 (2)
1、普通背包问题： (2)
2、棋盘覆盖问题： (2)
二、问题分析 (2)
1、普通背包问题： (2)
2、棋盘覆盖问题： (3)
三、建立数学模型 (3)
1、普通背包问题： (3)
四、算法设计 (4)
2、普通背包问题： (4)
2、棋盘覆盖问题： (4)
五、算法实现 (5)
1、普通背包问题： (5)
2、棋盘覆盖问题： (8)
六、测试分析 (9)
1、普通背包问题： (9)
2、棋盘覆盖问题： (11)
七、结论 (12)
八、源程序 (12)
1、普通背包问题： (12)
2、棋盘覆盖问题： (15)
九、参考文献： (16)
一、问题描述
1、普通背包问题：
有一个背包容量为C，输入N个物品，每个物品有重量S[i]，以及物品放入背包中所得的收益P[i]。求选择放入的物品，不超过背包的容量，且得到的收益最好。物品可以拆分，利用贪心算法解决。
2、棋盘覆盖问题：
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
二、问题分析
1、普通背包问题：
贪心算法的基本思想是：从问题的某一个初始解出发逐
步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。
背包问题用贪心算法来解决，先求出每件物品的平均价值即p[i]/s[i]，然后每次选择利润p[i]/s[i]最大的物品装进背包，这样就使得目标函数增加最快，当
最后一种物品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。
2、棋盘覆盖问题：
将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
三、建立数学模型
（根据问题情况选择，不需要此步骤可不要）
1、普通背包问题：
求平均价值即p[i]/s[i]
约束条件：
c1<=0
四、算法设计
2、普通背包问题：
用贪心算法进行设计，贪心算法的基本思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。
int n物品个数double C 背包的容量
double s[M] 物品的重量（或大小）double p[M]物品的价值
void average(int n,double s[M],double p[M])//按照价值密度的降序排列函数；double c1 背包剩余容量totalp 物品的总价值
void bag(int n,double C,double s[M],double p[M],double x[M])求物品总价值的函数在求物品总价值函数中药调用average函数，在主函数中调用bag()函数。
2、棋盘覆盖问题：
采用分治法设计，分治法的基本思想：分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。
将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
tr: 棋盘左上方格行号；
tc：棋盘左上方格列号；
dr：特殊方格所在行号；
dc：特殊方格所在列号；
size：棋盘规格2k×2k
五、算法实现
1、普通背包问题：
（1）实现了按照价值密度的降序排列：
void average(int n,double s[M],double p[M])
{int i,j;
double temp1,temp2,temp3,c[M];
for(i=1;i<=n;i++)
c[i]=p[i]/s[i];
for(i=1;i for(j=1;j<=n-i;j++) if(c[j] { temp1=p[j];p[j]=p[j+1];p[j+1]=temp1; temp2=s[j];s[j]=s[j+1];s[j+1]=temp2; temp3=c[j];c[j]=c[j+1];c[j+1]=temp3; } }; （2）求最大总价值： void bag(int n,double C,double s[M],double p[M],double x[M]) { int i; double c1; average(n,s,p); c1=C; while(c1!=0) {for(i=1;i<=n;i++) {if(s[i]<=c1) {x[i]=1; c1=c1-s[i];} else if(s[i]>c1) {x[i]=c1/s[i]; c1=0;}// totalp=totalp+p[i]*x[i]; }}}; （3）主函数： void main() { int i,n; double C=0,totalp=0,s[M],p[M],x[M]; char ch; while(1) { display(n,C,s,p); bag(n,C,s,p,x);//totalp cout<<"结果表示为:"< for(i=1;i<=n;i++) cout<<"第"< cout< cout<<"向量表示:"<<" ( "; for(i=1;i<=n;i++) { cout< totalp=totalp+p[i]*x[i];} cout<<")"< cout<<"背包的总价值为："< cin>>ch; if(ch=='Y'||ch=='y') continue; else break; }} 显示函数Display(): void display(int &n,double &C,double s[M],double p[M]) {int i; s[0]=0; p[0]=0; cout<<"请输入物体数n:"; cin>>n; cout< cout<<"请输入背包总容量C:"; cin>>C; cout< cout<<"请输入各物体的大小或重量:"< for(i=1;i<=n;i++) cin>>s[i]; cout<<"请输入各物体的价值p:"< for(i=1;i<=n;i++) cin>>p[i]; cout< }; 2、棋盘覆盖问题： （1）棋盘覆盖分治实现： void chessBoard(int tr, int tc, int dr, int dc, int size) {if(size==1) return; int t=tile++; int s=size/2; if(dr chessBoard(tr, tc, dr, dc, s); else {board[tr+s-1][tc+s-1]=t; chessBoard(tr, tc, tr+s-1, tc+s-1, s);} if(dr chessBoard(tr, tc+s, dr, dc, s); else {board[tr+s-1][tc+s]=t; chessBoard(tr, tc+s, tr+s-1, tc+s, s);} if(dr>=tr+s && dc chessBoard(tr+s, tc, dr, dc, s); else {board[tr+s][tc+s-1]=t; chessBoard(tr+s, tc, tr+s, tc+s-1, s);} if(dr>=tr+s && dc>=tc+s) chessBoard(tr+s, tc+s, dr, dc, s); else {board[tr+s][tc+s]=t; chessBoard(tr+s, tc+s, tr+s, tc+s, s);} } （2）主函数： void main() { int size; cout<<"输入棋盘的size(大小必须是2的n次幂): "; cin>>size; int index_x,index_y; cout<<"输入特殊方格位置的坐标: "; cin>>index_x>>index_y; chessBoard(0,0,index_x,index_y,size); for(int i=0;i { for(int j=0;j cout< cout< } } 六、测试分析 1、普通背包问题： （1）、输入物品个数n=3 （2）、输入背包容量C：10 （3）、输入各物品的大小或重量：6 、 5 、 5 （4）、输入各物品的价值p：56 、 23 、 43 2、棋盘覆盖问题： （1）、输入size：8 （2）、输入特殊方块的位置:1,1 七、结论 两个算法，普通背包问题是用的贪心算法设计的，棋盘覆盖问题是用的分治法设计的。在开始设计时对贪心算法和分治算法的思想很好理解，但是在设计算法时大概思路还是有的，但写完算法写代码是发现写不出来，原因就是算法设计的还不够细，后来上网查了些资料，分析了别人的算法，最终实现了现在的算法设计。在这两个算法中贪心算法求普通背包问题，基本上已经实现了主要的功能，在分治算法求棋盘覆盖问题，也基本上实现了它的功能，但在输入时还有不足，需要人工输入2的指数幂，不够方便。不过总的来说这次实践收获很多，不仅对先前学到的知识进行了巩固，还在应用实践中获得了经验。 八、源程序 1、普通背包问题： #include #define M 100 void display(int &n,double &C,double s[M],double p[M]) { int i; s[0]=0;p[0]=0; cout<<"请输入物体数n:"; cin>>n; cout< cout<<"请输入背包总容量C:"; cin>>C; cout< cout<<"请输入各物体的大小或重量:"< for(i=1;i<=n;i++) cin>>s[i]; cout<<"请输入各物体的价值p:"< for(i=1;i<=n;i++) cin>>p[i]; cout< }; void average(int n,double s[M],double p[M])//按照价值密度的降序排列； { int i,j; double temp1,temp2,temp3,c[M]; for(i=1;i<=n;i++) c[i]=p[i]/s[i]; for(i=1;i for(j=1;j<=n-i;j++) if(c[j] { temp1=p[j];p[j]=p[j+1];p[j+1]=temp1; temp2=s[j];s[j]=s[j+1];s[j+1]=temp2; temp3=c[j];c[j]=c[j+1];c[j+1]=temp3; } }; void bag(int n,double C,double s[M],double p[M],double x[M])//totalp(总价值) { int i; double c1; average(n,s,p); c1=C; while(c1!=0) { for(i=1;i<=n;i++) { if(s[i]<=c1) { x[i]=1; c1=c1-s[i]; } else if(s[i]>c1) { x[i]=c1/s[i]; c1=0; }// totalp=totalp+p[i]*x[i]; }}}; void main() { int i,n; double C=0,totalp=0,s[M],p[M],x[M]; char ch; while(1) { display(n,C,s,p); bag(n,C,s,p,x);//totalp cout<<"结果表示为:"< for(i=1;i<=n;i++) cout<<"第"< cout< cout<<"向量表示:"<<" ( "; for(i=1;i<=n;i++) { cout< totalp=totalp+p[i]*x[i];} cout<<")"< cout<<"背包的总价值为："< cout<<"按Y或y继续操作，否则按任意键"< cin>>ch; if(ch=='Y'||ch=='y') continue; else break; } } 2、棋盘覆盖问题： #include int tile=1; int board[100][100]; void chessBoard(int tr, int tc, int dr, int dc, int size) { if(size==1) return; int t=tile++; int s=size/2; if(dr chessBoard(tr, tc, dr, dc, s); else { board[tr+s-1][tc+s-1]=t; chessBoard(tr, tc, tr+s-1, tc+s-1, s);} if(dr chessBoard(tr, tc+s, dr, dc, s); else { board[tr+s-1][tc+s]=t; chessBoard(tr, tc+s, tr+s-1, tc+s, s); } if(dr>=tr+s && dc chessBoard(tr+s, tc, dr, dc, s); else { board[tr+s][tc+s-1]=t; chessBoard(tr+s, tc, tr+s, tc+s-1, s);} if(dr>=tr+s && dc>=tc+s) chessBoard(tr+s, tc+s, dr, dc, s); else { board[tr+s][tc+s]=t; chessBoard(tr+s, tc+s, tr+s, tc+s, s);}} void main() { int size; cout<<"输入棋盘的size(大小必须是2的n次幂): "; cin>>size; int index_x,index_y; cout<<"输入特殊方格位置的坐标: "; cin>>index_x>>index_y; chessBoard(0,0,index_x,index_y,size); for(int i=0;i { for(int j=0;j cout< cout< } } 九、参考文献： 《算法设计与分析》第二版吕国英版清华大学出版社 实验三01背包问题不同算法设计、分析与对比一．问题描述 给定n种物品和一背包。物品i的重量是w i ，其价值为v i ，背包的容量为c。 问题：应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 说明：在选择装入背包的物品时，对每种物品i只有两个选择，装入背包或不装入背包，也不能将物品装入背包多次。 二．实验内容与要求 实验内容： 1.分析该问题适合采用哪些算法求解（包括近似解）。 ^ 动态规划、贪心、回溯和分支限界算法。 2.分别给出不同算法求解该问题的思想与算法设计，并进行算法复杂性分析。 动态规划： 递推方程： m(i,j) = max{m(i-1,j),m(i-1,j-wi)+vi} j >= wi; m(i-1,j) j < wi; 时间复杂度为O(n). 贪心法： ^ 算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。但是，贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 用贪心法设计算法的特点是一步一步地进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中， 直到把所有数据枚举完，或者不能再添加为止。 回溯法： 回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。 对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 时间复杂度为：O(2n) 空间复杂度为：O(n) ： 分支限界算法： 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。 3.设计并实现所设计的算法。 4.对比不同算法求解该问题的优劣。 这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的，当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大到小取即可。当一件背包物品不可分割的时候，（因为不可分割，所以就算按物品的单位体积的价值大的先取也不一定是最优解）此时使用贪心是不对的，应使用动态规划。 5.需要提交不同算法的实现代码和总结报告。 动态规划方法： public class Knapsack { 《算法分析与设计》 课程实验 专业年级：信息与计算科学 学生学号： 学生姓名： 实验题目：用贪婪法求解背包问题 指导老师： 实验时间：20xx年xx月x日 一、实验内容 用贪婪法求解背包问题 要求：用非递归实现 二、实验步骤 2.1、理解算法思想和问题要求； 2.2、写出每个操作的算法 非递归算法： greedbag() { int N; int c; int[] w; int[] v; Scanner scan=new Scanner(System.in); System.out.print("输入背包的容量:"); c=scan.nextInt(); System.out.print("输入物品的数量:"); N=scan.nextInt(); System.out.print("分别输入物品的价值:"); v=new int[N]; for(int i=0;i 《算法分析与设计》实验报告 2015-2016年第2学期 实验班级： 学生姓名： 学号： 指导老师： 信息工程学院 实验项目名称：回溯算法解决0-1背包问题 实验日期：2016年5 月18 日 一、实验类型：□√验证性□设计性 二、实验目的 掌握0—1背包问题的回溯算法 三、实验内容及要求 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 四、实验步骤 #include 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 01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。 01背包的状态转换方程f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] } f[i,j]表示在前i件物品中选择若干件放在承重为j 的背包中，可以取得的最大价值。 Pi表示第i件物品的价值。 决策：为了背包中物品总价值最大化，第i件物品应该放入背包中吗？ 题目描述： 有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最 首先要明确这张表是从右到左,至底向上生成的。 为了叙述方便，用e10单元格表示e行10列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为10的背包，那么这个背包的最大价值是6，因为e物品的重量是4，背包装的了，把e装进去后价值为6。然后是e9单元格表示背包承重9，只有物品e, e装进去后，背包价值为6，接着是e8, e7单元格，一直到e3单元格表示背包承重3，但物品e承重4，装不了，所以e3=0, 对于d10单元格，表示只有物品e，d时,承重为10的背包,所能装入的最大价值，是10，因为物品e,d这个背包都能装进去。对于承重为9的背包，d9=10,是怎么得出的呢？ 根据01背包的状态转换方程，需要考察两个值， 一个是f[i-1,j],对于这个例子来说就是e9的值6，另一个是f[i-1,j-Wi]+Pi； 在这里， f[i-1,j]表示我有一个承重为9的背包，当只有物品e可选时，这个背包能装入的最大价值 f[i-1,j-Wi]表示我有一个承重为4的背包（等于当前背包承重减去物品d的重量），当只有物品e可选时，这个背包能装入的最大价值 f[i-1,j-Wi]就是指单元格e4值为6，Pi指的是d物品的价值，即4 由于f[i-1,j-Wi]+Pi = 6 + 4 = 10 大于f[i-1,j] = 6，所以物品d应该放入承重为9的背包，所以d9=10. 算法实验报告 ---背包问题 实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优 值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 问题描述： 给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi， 背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中 物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入 或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，背包的 容积d，物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出 为最大的总价值。 问题分析: 标准0-1背包问题，MaxV表示前i个物品装入容量为j的背包中时所能产生的最大价值，结构体objec表示每一个可装入物品，其中w表示物品的重量，v表示物品的价值。如果某物品超过了背包的容量，则该物品一定不能放入背包，问题就变成了剩余i-1个物品装入容量为j的背包中所能产生的最大价值；如果该物品能装入背包，问题就变成i-1个物品装入容量为j-objec[i].w的背包所能产生的最大价值加上物品i的价值objec[i].v. 复杂性分析 时间复杂度，最好情况下为0，最坏情况下为：（abc） 源程序 #include 南京信息工程大学实验（实习） 报告 实验（实习）名称 0—1背包实验（实习）日期得分指导教师 专业软件工程年级 11 班次姓名学号 一：实验目的 通过运用回溯法的深度优先搜索解决０－１背包问题，掌握运用回溯法解题。二：算法思想 回溯法的基本思想是按深度优先策略，从根节点出发搜索解空间树，算法搜索至解空间的任一点时，先判断该结点是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯，否则，进入该子树，继续按深度优先进行搜索。 三：算法实现 #include return b; } template 兰州交通大学数理与软件工程学院 题目0-1背包问题算法实现 院系数理院 专业班级信计09 学生姓名雷雪艳 学号200905130 指导教师李秦 二Ｏ一二年六月五日 一、问题描述： 1、0—1背包问题：给定n 种物品和一个背包，背包最大容量为M ，物 品i 的重量是w i ,其价值是平P i ，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大？ 背包问题的数学描述如下： 2、要求找到一个n 元向量(x1，x2…xn)，在满足约束条件： ????? ≤≤≤∑1 0i i i x M w x 情况下，使得目标函数 p x i i ∑max ，其中，1≤i ≤n ；M>0； wi>0；pi>0。满足约束条件的任何向量都是一个可行解，而使得目标函数 达到最大的那个可行解则为最优解[1]。 给定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, 使得 M w x i i ≤∑ ，而且 p x i i ∑达到最大[2]。 二、解决方案： 方案一：贪心算法 1、贪心算法的基本原理与分析 贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。 贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 2、0-1背包问题的实现 对于0-1背包问题，设A 是能装入容量为c 的背包的具有最大价值的物品集合，则Aj=A-{j}是n-1个物品1,2,...,j-1,j+1,...,n 可装入容量为c-wj 的背包的具有最大价值的物品集合。 用贪心算法求解0-1背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi ；然后，将物品进行排序，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c ，则选择单位重量价值次高的物品并尽可能多地装入背包。 数学与物理科学学院 《算法分析与设计》课程考查论文 题目0-1背包问题研究及算法策略比较分析 专业 班级 学号 姓名 任课教师 完成日期2011/5/24 背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。 那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用回溯法对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决0-1背包问题对这四种算法进行详细的比较，总结这种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。 摘要 (2) 一、绪论 (4) 1.1问题的研究及意义 (4) 1.20-1背包问题的算法研究与分析 (4) 1.3课题的主要研究内容 (4) 二、0-1背包问题在动态规划中的实现 (5) 2.1动态规划的基本原理与分析 (5) 2.20-1背包问题的实现 (5) 三、0-1背包问题在分枝-限界法中的实现 (7) 3.1分枝-限界法的基本原理与分析 (7) 3.20-1背包问题的实现 (7) 四、0-1背包问题在遗传算法中的实现 (9) 4.1遗传算法的基本原理与分析 (9) 4.20-1背包问题的实现 (10) 五、0-1背包问题在回溯法中的实现 (11) 5.1回溯法的基本原理与分析 (11) 5.20-1背包问题的实现 (11) 5.30-1背包问题在回溯法中的算法描述 (12) 5.4算法效率 (14) 5.5运行结果 (15) 六、四种算法的比较与分析 (15) 七、附录 (17) 一、实验目的与要求 掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对回溯法、分支限界法的理解。 1．要求分别用回溯法和分支限界法求解0-1背包问题； 2．要求交互输入背包容量，物品重量数组，物品价值数组； 3．要求显示结果。 二、实验方案 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。 三、实验结果和数据处理 1．用回溯法解决0-1背包问题： 代码： import java.util.*; public class Knapsack { private double[] p,w;//分别代表价值和重量 private int n; private double c,bestp,cp,cw; private int x[]; //记录可选的物品 private int[] cx; public Knapsack (double pp[],double ww[],double cc) { this.p=pp;this.w=ww;this.n=pp.length-1; this.c=cc;this.cp=0;this.cw=0; this.bestp=0; x=new int[ww.length]; cx=new int[pp.length]; } void Knapsack() { backtrack(0); } void backtrack(int i) { if(i>n) { //判断是否到达了叶子节点 if(cp>bestp) { for(int j=0;j 计算机算法设计与分析习 题及答案 Prepared on 24 November 2020 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 实验五：贪心算法求解背包问题 实验内容 应用贪心算法求解离散背包问题，分析时间复杂度。 有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vi（1<=i<=n），设求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 算法思想 ?动态规划的思想： –对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，求解出较大问题的解，直到求解出最大问题的解。 – 引进一个二维数组ch[MAX][MAX]，用ch[i][j]记录CH1与CH2的LCS 的长度，b[i][j]记录ch[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。 我们是自底向上进行递推计算，那么在计算ch[i,j]之前，ch[i-1][j-1]， ch[i-1][j]与ch[i][j-1]均已计算出来。此时我们根据CH1 [i] = CH2[j]还是CH1[i] != CH2[j]，就可以计算出ch[i][j]。 算法 length(string CH1,string CH2,int b[MAX][MAX]) //用于构建动态数组 //输入：两字符窜 //输出：最长公共子序列 for(i=1;i<=ch1Len;i++)//二重循环求解 for(int j=1;j<=ch2Len;j++) { if(CH1[i-1]==CH2[j-1])//相等字符 { ch[i][j]=ch[i-1][j-1]+1; b[i][j]=0; } else if(ch[i-1][j]>=ch[i][j-1])//上比较大 { ch[i][j]=ch[i-1][j]; b[i][j]=1; } else//左比较大 { ch[i][j]=ch[i][j-1]; b[i][j]=-1; } } printCS(int b[MAX][MAX],string x,int i,int j) //回溯求出最长子序列输出 //输入：标记数组 //输出：最长子序列 if(i == 0 || j == 0)//边界，返回 return; if(b[i][j] == 0) { printCS(b, x, i-1, j-1);//左上 cout< 算法设计与分析的复习要点 第一章：算法问题求解基础 算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 一．算法的五个特征： 1．输入：算法有零个或多个输入量； 2．输出：算法至少产生一个输出量； 3．确定性：算法的每一条指令都有确切的定义，没有二义性； 4．可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现； 5．有穷性：算法必须总能在执行有限步之后终止。 二．什么是算法？程序与算法的区别 1．笼统地说，算法是求解一类问题的任意一种特殊的方法；较严格地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 2．程序是算法用某种程序设计语言的具体实现；算法必须可终止，程序却没有这一限制；即：程序可以不满足算法的第5个性质“有穷性”。 三．一个问题求解过程包括：理解问题、设计方案、实现方案、回顾复查。 四．系统生命周期或软件生命周期分为： 开发期：分析、设计、编码、测试；运行期：维护。 五．算法描述方法：自然语言、流程图、伪代码、程序设计语言等。 六．算法分析：是指对算法的执行时间和所需空间的估算。算法的效率通过算法分析来确定。 七．递归定义：是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况和递归部分； 基础情况：以直接形式明确列举新事物的若干简单对象； 递归部分：有简单或较简单对象定义新对象的条件和方法 八．常见的程序正确性证明方法： 1.归纳法：由基础情况和归纳步骤组成。归纳法是证明递归算法正确性和进行算法分析的强有力工具； 2.反证法。 第二章：算法分析基础 一．会计算程序步的执行次数（如书中例题程序2-1,2-2,2-3的总程序步数的计算）。二．会证明5个渐近记法。（如书中P22-25例2-1至例2-9） 三．会计算递推式的显式。（迭代法、代换法，主方法） 四．会用主定理求T(n)=aT(n/b)+f(n)。（主定理见P29，如例2-15至例2-18）五．一个好的算法应具备的4个重要特征： 1.正确性：算法的执行结果应当满足预先规定的功能和性能要求； 2.简明性：算法应思路清晰、层次分明、容易理解、利于编码和调试； 3.效率：算法应有效使用存储空间，并具有高的时间效率； 4.最优性：算法的执行时间已达到求解该类问题所需时间的下界。 六．影响程序运行时间的主要因素： 1.程序所依赖的算法； 2.问题规模和输入数据规模； 3.计算机系统性能。 七．1.算法的时间复杂度：是指算法运行所需的时间； 算法分析与设计实验报告 第 4 次实验 } 附录：完整代码 #include 算法设计与分析大作业 班级：电子154 姓名：吴志勇 学号： 1049731503279 任课老师：李瑞芳 日期： 2015.12.25 算法设计与分析课程论文 0-1背包问题的算法设计策略对比与分析 0 引言 对于计算机科学来说，算法的概念是至关重要的。在一个大型软件系统的开发中，设计出有效的算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此，《算法分析与设计》成为计算科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。通过老师的解析，培养我们怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算法为例，对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算法的思维方式，改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。 1 算法复杂性分析的方法介绍 算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需的资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。对计算机资源，最重要的是时间与空间（即存储器）资源。因此，算法的复杂性有时间复杂性T(n)与空间复杂性S(n)之分。 算法复杂性是算法运行所需要的计算机资源的量，这个量应集中反映算法的效率，并从运行该算法的实际计算机中抽象出来，换句话说，这个量应该只依赖要解决的问题规模‘算法的输入和算法本身的函数。用C表示复杂性，N,I和A表示问题的规模、算法的输入和算法本身规模，则有如下表达式： C=F(N,I,A) T=F(N，I,A) S=F(N，I,A) 其中F(N,I,A)是一个三元函数。通常A隐含在复杂性函数名当中，因此表达式中一般不写A。 即：C=F(N,I) T=F(N,I) S=F(N,I) 算法复杂性中时间与空间复杂性算法相似，所以以下算法复杂性主要以时间复杂性为例： 算法的时间复杂性一般分为三种情况：最坏情况、最好情况和平均情况。下面描述算法复杂性时都是用的简化的复杂性算法分析，引入了渐近意义的记号O,Ω，θ，和o。 O表示渐近上界Ω表示渐近下界： θ表示同阶即：f(n)= O(g(n))且 f(n)= Ω（g(n)） 2 常见的算法分析设计策略介绍 2.1 递归与分治策略 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 递归算法举例： 共11页第1页 背包问题算法设计 题目描述： 有n个物品，每个物品的重量为w[i]，取物品则效益增加p[i]，对于给定的一个能容纳重量为M的背包，怎样装包才能使获得的效益最大？每个物品的取值为x[i]，x[i]=0/1，0表示该物品不装包，1表示将该物品装入包中。 以上描述就是一个经典的0/1背包问题。 输入输出： 输入一个n，然后输入w[1,2,...,n],p[1,2,...,n] 输出最大效益值和x[1,2,...,n]用0/1表示 sampleinput 3//n 234//w[i] 125//p[i] sampleoutput 6//最大效益值 101//x[i] 解题思路： 假定决策次序为x[n],x[n-1],...,x[1]。在对x[n]做出决策之后，问题处于下列两种状态之一： 背包的剩余容量为M，没有产生任何效益； 剩余容量是M-w，效益增长了p。 显然，余下来的x[n-1],x[n-2],..,x[1]的决策相对于x所产生的问题状态应该是最优的，否则x[n],x[n-1],...,x[1]就不能是最优决策序列。 设f[j][x]是从物品1-j,背包容量为x的最优解 则最优序列的解f[n][m] 对于任意的f[i][x]=max{f[i-1][x],f[i-1][x-wi]+pi}---------------------------（1） 为了能向后递推而最后求出f[n][m],需要从f[0][x]开始。对于所有x>=0，有f[0][x]=0， 当x<0时，有f[0][x]=负无穷。根据（1）马上可解出0<=x 基于遗传算法的0-1背包问题的求解 摘要： 一、前言 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于NP 完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。 遗传算法已经成为组合优化问题的近似最优解的一把钥匙。它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。 背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题， 其 计算复杂度为 )2(O n ，传统上采用动态规划来求解。设w[i]是经营活动 i 所需要的资源消耗，M 是所能提供的资源总量，p[i]是人们经营活动i 得到的利润或收益，则背包问题就是在资源有限的条件下， 追求总的最大收益的资源有效分配问题。 二、问题描述 背包问题( Knapsack Problem)的一般提法是：已知n 个物品的重量（weight ）及其价值（或收益profit ）分别为0>i w 和0>i p ，背包的容量（contain ）假设设为0>i c ，如何选择哪些物品装入背包可以使得在背包的容量约束限制之内 所装物品的价值最大？ 该问题的模型可以表示为下述0/1整数规划模型： 目标函数：∑==n i i i n x c x x x f 1 21),,(max Λ ????? =∈≤∑=) ,2,1(}1,0{t .s 1n i x p x w i n i i i i Λ （*） 算法设计与分析 实验报告 —0/1背包问题 - 【问题描述】 给定n 种物品和一个背包。物品i 的重量是i w ，其价值为i v ，背包容量为C 。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 【问题分析】 0/1背包问题的可形式化描述为：给定C>0, i w >0, i v >0,1i n ≤≤，要求找出n 元0/1向量{}12(,,...,),0,1,1n i x x x x i n ∈≤≤，使得n 1i i i w x c =≤∑，而且 n 1 i i i v x =∑达到最大。因此0/1背包问题是一个特殊的整数规划问题。 0n k w ≤≤1 max n i i i v x =∑ n 1 i i i w x c =≤∑ {}0,1,1i x i n ∈≤≤ 【算法设计】 设0/1背包问题的最优值为m( i, j )，即背包容量是j ，可选择物品为i,i+1,…,n 时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m( i, j )的递归式如下： max{m( i+1, j ), m( i+1, j-i w )+i v } i j w ≥ m( i, j )= m(i+1,j) n v n j w > m(n,j)= 0 0n k w ≤≤ 【算法实现】 #include 算法设计与分析 —背包问题 - 【问题描述】 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。 【问题分析】 用贪心算法求解背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi；然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去，直到背包装满为止。 【算法设计】 因可以取物体的部分放入，故每次选择价值重量比最高的物体放入，可保证放入的价值一定最大，满足贪婪选择性质和最有子结构性质，故采用贪心算法求解： 1. 根据各个物体的价值p与重量w计算价值重量比v 2. 根据v降序排序 3. 从当前最大的v的开始，判断该物体重量是否超过背包剩余载重 4. 是则放入背包剩余载重量的物体，加上这部分的价值，跳到7 5. 否则将物体完整放入背包，加上物体的价值 6. 若还有物体未放入背包，则跳到3 7. 输出背包中物体的总价值 【算法实现】 #include 贪心算法实现01背包问题 算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。 具体实现过程是：首先可以设置一个备份pvu类型的数组，在不破环原数据的情况下，对此备份数组按单位重量价值从大到小的排序。依次设立两个指针i，j(其中i表示当前应该参与最佳pv值的元素指针，j表示符合约束条件的指针（单位重量价值PV最大，重量最小，不超过最大承重量约束) 代码实现如下： #include 01背包问题不同算法设计、分析与对比报告
算法设计实验_贪心算法背包问题
回溯算法解决0-1背包问题(DOC)
动态规划之01背包问题(最易理解的讲解)
算法设计背包问题
0-1背包问题_算法设计C++
0-1背包问题四种不同算法的实现要点
0-1背包问题研究及算法策略比较分析
算法 0-1背包问题
计算机算法设计与分析习题及答案
算法设计和分析实验四：贪心算法求解背包问题
最新算法设计与分析复习要点(1)
背包问题(贪心算法)
0-1背包问题的算法设计策略对比与讲解
背包问题算法设计
遗传算法的0-1背包问题(c语言)
算法设计与分析实验报告—01背包问题
算法设计与分析—背包问题
贪心算法实现01背包问题
相关主题
文本预览