万力27算法设计

《万力27算法设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法分析与设计》课程设计报告题目:学号:姓名:专业:班级:10415127万力信息与计算科学10级信计2013年7月一、问题描述：给定/?种物品和一个容量为C的背包，物品1的重量是刃，其价值为Vi,0/1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包中物品的总价值故大。利用冋溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量xi（xi=0或1,xi=0表示物体i不放入背包，xi=1表示把物体i放入背包），使得尽量多的价值装入背包。二、算法分析及思路：①分析要解决的问题，借助图表等辅助

2、表达。0-1背包问题用回溯法实现就是要枚举其所有的解空间，时间复杂度为0（2"）左右。搜索的具体方法如下：对于每一个物品i,对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树：基木思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。利用回溯算法写还可以加入一些优化，进行剪枝，因为很多情况是没有意义的，例如当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。或者将剩下的所有物品都选取其总价值也没有H前已

3、经求得的方案的价值还大的话，也是可以剪枝的。②分析解决该问题的方法可能会有怎样的时空复杂度。时间复杂度估计：0（2”）因为物品只有选与不选2个决策，而总共有n个y物品，所以时间复杂度为0（2〃）。空间复朵度估计：0(/7)因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复朵度为0(/2)o三、主要解决的设计问题：根据对问题的分析，写出解决办法。根据上面的分析，搜索的具体方法如下：对于每一个物品i,对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形

4、成了一棵解空间树，由父亲节点往下搜索的时候，往左表示选择该物品，并且将该物品的重量和价值追加到总重量和总价值中，最后，当到达第n+1层的时候，表示所有的物品都己经决策完了，可以比较和更新最优值。当所有的分支和节点都遍历完时，此时的最优值就是原问题的最优值。优化方法：剪枝一：可以进行剪枝，因为很多情况是没有意义的，当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。剪枝二：将剩下的所有物品都选取其总价值也没有日前已经求得的方案的价值还大的话，也可以返回。程序设计的流程图:五、输入和输出说明：1、数据输入：由文

5、件input.txt提供输入数据n,c,及每个物品的重量w[]和价值2、结果输出:程序运彳亍结束时，将最优解输出到文件output.txt中o输入文件示例输出文件示例input.txtoutput.txt41101213212102015六、程序及其注解:#includeintc;//背包容量intm;//物品数intx[100];intweight[100];//物品重量intprice[100];〃物品价值intbp=O;intbA[100];//当前最优解inttimes=0;voidbe

6、ibao(intn)inti,k;for(i=l;i<=n;i++)//初始化x[i]二0;k=l;whi1e(k>=l){times+=l;x[k]二x[k]+l;//第k个物品放入背包if(x[k]<=2&&k==m){〃得到一个解，输出intcurrer)tWeight=O;//当前車量intcurrentPrice=O;//当前价值for(i=l;i<=n;i++)if(x[i]==l)currentWeight+=weight[i];currentPrice+=price[i];}if(currentW

7、eight<=c){if(currentPrice>bp){bp二currentPrice;for(intj=l;j<=n;j++){if(x[j]=2)bA[j]=x[j]-2;elsebA[j]二x[j];}}}}elseif(x[k]<=2&&k

8、)：〃);scanf(”％d",&c);printf(，z请依次输入%d个物品的重量:",m);for(i=l;i<=m;i++)scanf("%d",&weight[订);printfC请依次输入%d个物品的价值:z，,m);for(i=l;i<=m;i++)seanf("%d",&price[i]);beibao(m);十Jr7^Jr7^7^"■

9、I

10、