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

算法报告班级：140710班组员：14071006魏泽琳14071008田恬14071019黄婧婧14071021宋蕊14071026于婷雯指导老师：徐旭东广义背包问题一、问题描述广义背包问题的描述如下：给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。请用数学语言对上述背包问题加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法的求解步骤。用一种你熟悉的程序设计语言加以实现。二、基本思路1、01背包问题在讨论广义背包问题前应该先讨论最基础的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件物品，那么问题就转化为“前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背包的区别：每种物品都有无限件，能放多少就放多少。问题:在不超过背包重量的情况下，能获得的最大价值。举例：物品个数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指此时背包重量)//初始条件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]=w[j]，则将物品j去掉，不用考虑。(c=Cost价格，w=Weight重量）即，如果一个物品A是占的地少且价值高，而物品B是占地多，但是价值不怎么高，那么肯定是优先考虑A物品的。TSP问题一、问题描述所谓TSP问题是指旅行商要去n个城市推销商品，其中每个城市到达且仅到达一次，并且要求所走的路程最短（该问题又称货郎担问题、邮递员问题、售货员问题等）。TSP问题最容易想到、也肯定能得到最优解的算法是穷举法，即考察所有可能的行走线路，从中选出最佳的一条。但是用穷举法求解TSP问题的时间复杂性为O(n!)，属于NP问题。请用数学语言对该TSP问题加以抽象，在此基础上给出动态规划求解该问题的递推公式。要求对所给公式中的符号意义加以详细说明，并简述算法求解步骤。用一种你熟悉的程序设计语言加以实现。二、基本思路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的距离）举例：node0123053215792371232912i/Vj{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}021151011212312141832141519三、算法伪代码for(i=1;in;i++)//初始化第0列d[i][0]=c[i][0];for(j=1;j2^(n-1)-1;j++)｛for(i=1;in;i++){if(子集Vj中不包含i){对Vj中的每个元素k，计算d[i][Vj]=min{c[i][k]+d[k][{Vj-k}]|每一个k∈Vj};}}对V[2^(n-1)-1]中的每个元素k,计算:d[0][2^(n-1)-1]=min{c[0][k]+d[k][2^(n-1)-2]};输出最短路径:d[0][2^(n-1)-1];}广义背包问题源代码：#includeiostream#includevector#includeassert.h#includewindows.h#includestdio.h#includewindef.h#includeiostream#includeassert.husingnamespacestd;/*f[i][m]:前i件物品放入背包容量为m的背包获得的最大收益f[i][m]=max(f[i-1][m],f[i-1][m-k*Wi]+k*Vi,其中1=k=m/Wi)边界条件f[0][m]=0;f[m][0]=0;*/constintN=4;//四种物品constintM=6;//背包的容积为6intweight[N+1]={0,1,2,3,4};//四种物品的重量分别为1,2,3,4intValue[N+1]={0,5,10,15,25};//四种物品的价值分别为5,10,20,25intf[N+1][M+1]={0};//f[i][m]初始化为零intCompleteknapsack(){//边界条件for(inti=0;i=N;i++)f[i][0]=0;for(intm=0;m=M;m++)f[0][m]=0;//递推for(i=1;i=N;i++){for(m=1;m=M;m++){f[i][m]=0;intnCount=m/weight[i];//背包最多能装入的同种物品数量for(intk=0;k=nCount;k++){f[i][m]=max(f[i][m],f[i-1][m-k*weight[i]]+k*Value[i]);//最优值函数}}}returnf[N][M];}intmain(){coutCompleteknapsack()endl;//输出return0;}