枚举回溯动态规划解决01背包问题课程设计论文
12页1、 一、 问题描述01背包问题: 一个商人带着一个能装m千克的背包去收购货物。现有n种货物,且第i种货物有wi千克,可获得pi元。假设货物不能拆零,请编写算法帮助商人收购货物,获得最高利润。二、 算法设计与分析枚举法分析: 设n个物品的重量和价值分别存储于数组w 和v 中,限制重量为tw.考虑一个n元组(x0,x1,xn-1),其中xi=0 表示第i个物品没有选取,而xi=1则表示第i个物品被选取。用枚举法解决背包问题,需要枚举所有的选取方案,而根据上述方法,我们只要枚举所有的n元组,就可以得到问题的解。 显然,每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数,且这些二进制数的取值范围为02n-1.因此,如果把02n-1分别转化为相应的二进制数,则可以得到我们所需要的2n个n元组。 回溯法分析: 先确定搜索空间:n件物品的取舍数字化,”取”标识为1,否则为0,则搜索的空间为一维数组如:(0,0,0、0,0),(0,0,0、0,1),(0,0,0、10)、(1,1,1、1,1)这是一颗子集树确定约束条件:所取物品的质量和不超过m,只有取当前物品时才
2、需要判断所取的质量和不超过m,若不取当前物品时,就无需进行判断,只要一步步进行搜索。搜索过程中的主要操作:累加所取物品的质量,回溯是还要做现场清理,也就是将当前的物品置为不取状态,且从累加质量中减去当前物品的质量。动态规划法:0-1背包问题可以看作是寻找一个序列,对任一个变量 的判断是决定=1还是之后,已经确定了,在判断时,会有两种情况:(1) 背包容量不足以装入物品i,则=0,背包的价值不增加;(2) 背包的容量可以装下物品i,则=1,背包的价值增加。这两种情况下背包的总价值的最大者应该是对判断后的价值。 我们可以一步一步的解出我们所需要的解。第一步,只装入第一个物品,确定在各种情况下背包能得到的最大价值;第二步,只装入前两个物品,确定在各种情况下的背包能够得到的最大价值;一次类推,到了第n步就得到我们所需要的最优解了。三、 测试分析1) 枚举法对于一个有n个元素的集合,其子集数量为,所以,不论生成子集的算法效率有多高,穷举法都会导致一个的算法。2) 回溯法由于计算上界的函数需要O(n)时间,在最坏情况下有个右儿子结点需要计算上界,所以解0-1背包问题的回溯法算法所需要的计算时间为3
3、) 动态规划由于函数中有一个两重for循环,所以时间复杂度为O(n+1)x(m+1).空间复杂度也是O(n+1)x(m+1),即O(nm).四、 附录:源代码1) 枚举法#include using namespace std;#include #define MAX 100 #include #include/将n化为二进制形式,结果存放到数组b中void conversion(int n,int bMAX) int i; for(i=0;iMAX;i+) bi = n%2; n = n/2; if(n=0)break; void main()long start,end;start=clock();int i,j,n,bMAX,tempMAX; float tw,maxv,wMAX,vMAX,temp_w,temp_v; coutn; / 输入物品个数 couttw; / 输入背包的限制重量 /输入各个物品的重量 coutplease input the weight : ; for(i=0;iwi; /输入各个物品的价值 coutplease input the value :
《枚举回溯动态规划解决01背包问题课程设计论文》由会员工****分享,可在线阅读,更多相关《枚举回溯动态规划解决01背包问题课程设计论文》请在金锄头文库上搜索。
关于橡胶产业发展的调查报告
2023固定资产借款合同标准范本(三篇).doc
旅行社合作协议书集锦7篇
动产质押借款合同.doc
装潢采购合同.doc
沪教版四年级英语上学期句型转换考前练习
甘肃省酒泉市高三上学期化学期末考试试卷
初级护师考试基础知识真题及答案
电流表电压表功率表及电阻表检定规程
四年级观察假山日记500字.doc
用此方法保证能使你的孩子考上全国重点大学
土地资源调查与评价实习报告
《12.2滑轮》教案
盐城存储芯片项目建议书(模板参考)
构造地质学教案
中药材种植实用技术
小学体育立定跳远教学设计
校园元旦晚会的活动总结(二篇).doc
学期教学工作计划高中语(三篇).doc
液化可燃气泄漏的预防措施
2023-12-29 6页
2022-12-04 35页
2023-06-30 8页
2023-01-20 5页
2023-04-02 4页
2023-08-17 6页
2023-04-08 10页
2023-02-22 13页
2023-11-02 9页
2022-12-27 9页