01背包问题毕业论文

1．0-1背包： 每个背包只能使用一次或有限次(可转化为一次)： A.求最多可放入的重量。 NOIP2001 装箱问题 有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。 l 搜索方法 procedure search(k,v:integer); {搜索第k个物品，剩余空间为v} var i,j:integer; begin if v=best then exit; {s[n]为前n个物品的重量和} if k<=n then begin if v>w[k] then search(k+1,v-w[k]); search(k+1,v); end; end; l DP F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。 实现:将最优化问题转化为判定性问题 f [I, j] = f [ i-1, j-w[i] ] (w[I]<=j<=v) 边界：f[0,0]:=true. For I:=1 to n do For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]]; 优化：当前状态只与前一阶段状态有关，可降至一维。 F[0]:=true; For I:=1 to n do begin F1:=f; For j:=w[I] to v do If f[j-w[I]] then f1[j]:=true; F:=f1; End; B.求可以放入的最大价值。 F[I,j] 为容量为I时取前j个背包所能获得的最大价值。 F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] } C.求恰好装满的情况数。 DP: Procedure update; var j,k:integer; begin c:=a; for j:=0 to n do if a[j]>0 then if j+now<=n then inc(c[j+now],a[j]); a:=c; end; 2．可重复背包 A求最多可放入的重量。 F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。 状态转移方程为 f[I,j] = f [ I-1, j – w[I]*k ] (k=1.. j div w[I]) B.求可以放入的最大价值。 USACO 1.2 Score Inflation 进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti（解答此题所需的时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。 *易想到： f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] } (0<=k<= i div w[j]) 其中f[i,j]表示容量为i时取前j种背包所能达到的最大值。 *实现： Begin FillChar(f,SizeOf(f),0); For i:=1 To M Do For j:=1 To N Do If i-problem[j].time>=0 Then Begin t:=problem[j].point+f[i-problem[j].time]; If t>f[i] Then f[i]:=t; End; Writeln(f[M]); End. C.求恰好装满的情况数。 Ahoi2001 Problem2 求自然数n本质不同的质数和的表达式的数目。 思路一，生成每个质数的系数的排列，在一一测试，这是通法。 procedure try(dep:integer); var i,j:integer; begin cal; {此过程计算当前系数的计算结果，now为结果} if now>n then exit; {剪枝} if dep=l+1 then begin {生成所有系数} cal; if now=n then inc(tot); exit; end; for i:=0 to n div pr[dep] do begin xs[dep]:=i; try(dep+1); xs[dep]:=0; end; end; 思路二，递归搜索效率较高 procedure try(dep,rest:integer); var i,j,x:integer; begin if (rest<=0) or (dep=l+1) then begin if rest=0 then inc(tot); exit; end; for i:=0 to rest div pr[dep] do try(dep+1,rest-pr[dep]*i); end; {main: try(1,n); } 思路三：可使用动态规划求解 USACO1.2 money system V个物品，背包容量为n，求放法总数。 转移方程： Procedure update; var j,k:integer; begin c:=a; for j:=0 to n do if a[j]>0 then for k:=1 to n div now do if j+now*k<=n then inc(c[j+now*k],a[j]); a:=c; end; {main} begin read(now); {读入第一个物品的重量} i:=0; {a[i]为背包容量为i时的放法总数} while i<=n do begin a[i]:=1; inc(i,now); end; {定义第一个物品重的整数倍的重量a值为1，作为初值} for i:=2 to v do begin read(now); update; {动态更新} end; writeln(a[n]);

1楼的不是遗传算法吧！刚好做过这个遗传算法解背包问题的论文，给你回答啦~~独家哦，分数要给偶~~1、程序开发环境 开发环境：Visual C++6.0 (把Fortran程序改为VC) 操作系统：Windows 2003 Professional2、程序性能对比 运行时间与加速比（如表1所示）进程数p（个） 1 2 4 运行时间t（秒） 129s 78s 38s 加速比s 1.65 3.38 表1、运行时间与加速比3、程序运行结果： 实例数据： 假设物体的重量Weight、物体的收益Profit和背包的容量Contain 分别为：Weight={ 80，82，85，70，72， 70，66，50，55，25 ， 50，55，40，48，50， 32，22，60，30，32 ， 40，38，35，32，25， 28，30，22，50，30 ， 45，30，60，50，20 ， 65，20，25，30，10 ， 20，25，15，10，10 ， 10，4， 4， 2， 1 }Profit={ 220，208，198，192，180， 180，165，162，160，158， 155，130，125，122，120 ， 118，115，110，105，101， 100，100，98， 96， 95， 90， 88， 82， 80， 77 ， 75， 73， 72， 70， 69， 66， 65， 63， 60， 58， 56， 50， 30， 20， 15， 10， 8， 5， 3， 1}Contain=1000， 如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大? 传统的算法（动态规划、递归回溯法和贪心算法所得结果： 总价值为3077 , 总重量为999。 2001年张铃，张钹教授在计算机学报上发表的《佳点集遗传算法》所得结果 总价值为3103, 总重量为1000。 我们算法所得结果： 总价值为3103, 总重量为1000。 我们所求得最优解的个体分配情况为：11010 10111 10110 11011 01111 11101 00001 01001 10000 01000算法 最大迭代次数 总价值为 总重量为 传统的算法 400 3077 999 佳点集算法 70 3103 1000 遗传算法 75 3103 1000 // knapsack.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include #include #include #include #include #include // 重要常量参数#define popsize 200 //种群的规模#define pc 0.618 //杂交概率#define pm 0.03 //变异概率#define lchrom 50 //染色体长度#define maxgen 1000 //最大进化代数struct population{ unsigned int chrom[lchrom]; //染色体 double weight; //背包重量 double fitness; //适应度 unsigned int parent1,parent2,cross; //双亲、交叉点};//新生代种群、父代种群struct population oldpop[popsize],newpop[popsize]; //背包问题中物体重量、收益、背包容量int weight[lchrom],profit[lchrom],contain; //种群的总适应度、最小、最大、平均适应度 double sumfitness,minfitness,maxfitness,avgfitness;//计算适应度时使用的 惩罚函数系数double alpha;//一个种群中最大和最小适应度的个体int minpop,maxpop; /* 读入背包信息,并且计算惩罚函数系数 */void read_infor(){ FILE *fp; int j; //获取背包问题信息文件 if ((fp=fopen("knapsack.txt","r"))==NULL) { //读取文件失败 AfxMessageBox("The file is not found",MB_OK,NULL); return; } //读入物体收益信息 for (j=0;jmaxfitness)&&((int)(tmp_fit*10)%10==0)) { maxfitness=pop[i].fitness; maxpop=i; } //选择种群中最小适应度的个体 if (tmp_fitoldmax) { report(newpop,gen); } //保存新生代种群的信息到老一代种群信息空间 memcpy(&oldpop,&newpop,popsize*sizeof(struct population)); } printf("It is over."); getch();}

毕业论文答辩那天，跟我的心理咨询师考试是同一天，算不算是很衰的事情？

那是好几年前的事情了，当时我是大四的学生，一直在忙着毕业论文 毕业答辩的事情，而恰好，报考的心理咨询师考试，最后确认下来的考试时间，居然就是答辩的那天。

一开始收到消息的时候，我的人是懵逼的。

那我是心理咨询师考试比较重要呢，还是毕业答辩比较重要呢？

后来跟老师商量了一下，决定就先去考试，毕竟是全国的考试，不可能因为我一个人而更改时间，如果我要再考的话，就只能等到明年的考试时间。

同时也跟学校申请了暂缓毕业答辩。不过，正常的准备还是要做。

为了考试，每天都必须刷心理咨询师考试的试题，刷完题之后晚上还要总结，看看哪些知识点，哪些技能还需要巩固加强，哪些方面还需要再学习一下。

毕业论文写得差不多了，给老师拿去修改，老师也给予了肯定。然后开始制作ppt，我的ppt跟现在的ppt比较起来，没有什么高大上的特效，没有什么酷炫的版面，只有简简单单的架构，说明我为什么要写这个论文课题，是怎么写的，得出了什么结论，有哪些缺陷……给老师看过，老师说可以，就这样吧。然后我就安心备考了。把毕业答辩的事情暂时放下来，不过自己还是打印多了两份毕业论文，把毕业答辩的ppt随身带在背包里。

因为考试地点跟我所在的大学是跨省的关系，所以我们提前一天就去考点了。

在考点附近的国安宾馆住宿，然后收拾下榻之后，又是一番备战。还记得那天晚上，我们级的几个心理学的朋友，跟我这个教育学的一起混着，在互相考察背诵那些心理学的知识跟技能，分析案例，提醒别人自己遇到的易错点……

说实话吧，大学四年的学习，教育学跟心理学相关，加上我们宿舍六个人，就有三个是心理学专业的，所以考试可以说难度并没有那么大，而且通过率低是相对的，只要自己分数足够，答案正确，怎么样，都会通过……

不过当时考完已经没有心情了。其他人都还在打算在那边玩的时候，我已经搭上回学校的车了。打算赶着最后的时间，看看能不能完成答辩。

回到学校的时候，是下午的五点多，赶到答辩教室的时候，其他同学已经基本答辩完毕了。

我算是最后一个吧？

跟在现场做助理的老师说明情况，跟院长讲了一下缘由。院长跟教授都同意了，我是最后一个。

还好，我的ppt跟论文也准备着一直放在背包。

把准备好的论文给了老师，然后上多媒体讲台，打开ppt……开始毕业答辩流程……

最后，答辩顺利通过，心理咨询师考试也是。

其实很多时候，衰这个东西，真的不仅仅是运气问题，也是个人能力与选择的问题。不要怪运气，自己多努力一点，实际上，运气也会照顾你的。抱怨的话，反而会让运气越来越糟糕。你觉得呢？