背包问题和TSP问题算法报告.docx

《背包问题和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