欢迎来到天天文库
浏览记录
ID:59133970
大小:25.71 KB
页数:7页
时间:2020-09-12
《背包问题和TSP问题算法报告.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、算法报告班级:班组员:魏泽琳田恬黄婧婧宋蕊于婷雯指导老师:徐旭东广义背包问题一、问题描述广义背包问题的描述如下:给定载重量为M的背包和n种物品,每种物品有一定的重量和价值,现在需要设计算法,在不超过背包载重量的前提下,巧妙选择物品,使得装入背包的物品的总价值最大化。规则是,每种物品均可装入背包多次或不装入(但不能仅装入物品的一部分)。请用数学语言对上述背包问题加以抽象,在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明,并简述算法的求解步骤。用一种你熟悉的程序设计语言加以实现。二、基本思路1、01背包问题在讨论广义
2、背包问题前应该先讨论最基础的01背包问题。这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。用子问题定义状态:即F[i][m]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值。其状态转移方程是:F[i][m]=max{F[i−1][m],F[i−1][m−wi]+Ci}}这个方程是解决背包问题的关键点,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要解释一下:“将前i件物品放入容量为m的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只和前i−1件物品相关的问题。如果不放第i件物
3、品,那么问题就转化为“前i−1件物品放入容量为v的背包中”,价值为F[i−1][m];如果放第i件物品,那么问题就转化为“前i−1件物品放入剩下的容量为m−wi的背包中”,此时能获得的最大价值就是F[i−1][m−wi]再加上通过放入第i件物品获得的价值Ci。最优解的函数从方程中能得出:F[i][m]=F[i-1][m](当第i个物品不装入)F[i][m]>F[i-1][m](当第i个物品装入)以上是有关01背包的讨论,现在讨论广义背包的问题。2、广义背包问题与01背包的区别:每种物品都有无限件,能放多少就放多少。问题:在不超过背包重量的情况下,
4、能获得的最大价值。举例:物品个数N=3,背包重量为M=5,则背包可以装下的最大价值为40.如下表:基本思路(直接扩展01背包的方程)直接扩展01背包的方程:由于本问题类似于01背包问题,在01背包问题中,物品要么取,要么不取,而在广义背包中,物品可以取0件、取1件、取2件...直到背包放不下位置。因此,可以直接在01背包的递推式中扩展得到:F[i][m]:表示前i件物品放入重量为m的背包中时的最大价值递推式:F[i][m]=max(F[i–1][m],F[i-1][m-K*wi]+K*Ci);其中1<=K<=m/wi(m指此时背包重量)//初始条
5、件f[0][m]=0;f[i][0]=0;Value[i]为第i件物品的价值;矩阵图如下:f[i][m]第i件物品是否装入,此时容量为M的背包的最大价值0123456000000001051015252530200101520303530001520253040000202530此程序运行结果为35。复杂度分析:程序需要求解N*M个状态,每一个状态需要的时间为O(m/Weight[i]),所以总的复杂度为O(NM*Σ(M/Weight[i]))。思考:完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]
6、>=w[j],则将物品j去掉,不用考虑。(c=Cost价格,w=Weight重量)即,如果一个物品A是占的地少且价值高,而物品B是占地多,但是价值不怎么高,那么肯定是优先考虑A物品的。TSP问题一、问题描述所谓TSP问题是指旅行商要去n个城市推销商品,其中每个城市到达且仅到达一次,并且要求所走的路程最短(该问题又称货郎担问题、邮递员问题、售货员问题等)。TSP问题最容易想到、也肯定能得到最优解的算法是穷举法,即考察所有可能的行走线路,从中选出最佳的一条。但是用穷举法求解TSP问题的时间复杂性为O(n!),属于NP问题。请用数学语言对该TSP问题加
7、以抽象,在此基础上给出动态规划求解该问题的递推公式。要求对所给公式中的符号意义加以详细说明,并简述算法求解步骤。用一种你熟悉的程序设计语言加以实现。二、基本思路Length(总回路)=Length(S0→S1)+Length(S1→S2→S3→S0)把问题简化:把求通过各点的一条最短的回路→求解从某个(任意)确定点到回路最后一个点的最短路径。规范化公式:d(i,V)表示从i点经过点集V各点一次之后回到出发点的最短距离d(i,V’)=min{Cik+d(k,V–{k})}d(k,{})=Cik(其中,Cik表示i→k的距离)举例:node01230
8、53215792371232912i/Vj{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}02115101121231
此文档下载收益归作者所有