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

1、算法报告班 级： 140710班 组 员： 14071006 魏泽琳 14071008 田 恬 14071019 黄婧婧 14071021 宋 蕊 14071026 于婷雯 指导老师： 徐旭东 广义背包问题 一、问题描述广义背包问题的描述如下：给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。请用数学语言对上述背包问题加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法的

2、求解步骤。用一种你熟悉的程序设计语言加以实现。二、基本思路1、01背包问题在讨论广义背包问题前应该先讨论最基础的01背包问题。这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即Fim表示前i件物品恰放入一个重量为m的背包可以获得的最大价值。其状态转移方程是：Fim=maxFi1m,Fi1mwi+Ci这个方程是解决背包问题的关键点，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要解释一下：“将前i件物品放入容量为m的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前i1件物品相关的问题。如果不放第i件物品，那么问

3、题就转化为“前i1件物品放入容量为v的背包中”，价值为Fi1m；如果放第i件物品，那么问题就转化为“前i1件物品放入剩下的容量为mwi的背包中”，此时能获得的最大价值就是Fi1mwi再加上通过放入第i件物品获得的价值Ci。最优解的函数从方程中能得出:Fim=Fi-1m(当第i个物品不装入)Fim>Fi-1m(当第i个物品装入)以上是有关01背包的讨论，现在讨论广义背包的问题。2、广义背包问题与01背包的区别：每种物品都有无限件，能放多少就放多少。 问题:在不超过背包重量的情况下，能获得的最大价值。举例：物品个数N = 3，背包重量为M = 5，则背包可以装下的最大价值为40.如下表：基本

4、思路（直接扩展01背包的方程）直接扩展01背包的方程：由于本问题类似于01背包问题，在01背包问题中，物品要么取，要么不取，而在广义背包中，物品可以取0件、取1件、取2件.直到背包放不下位置。因此，可以直接在01背包的递推式中扩展得到：Fim:表示前i件物品放入重量为m的背包中时的最大价值递推式：Fim = max(Fi 1m,Fi -1m- K * wi+ K * Ci);其中 1 <= K <= m/wi(m指此时背包重量)/初始条件f0m = 0;fi0 = 0;Valuei为第i件物品的价值；矩阵图如下：fim第i件物品是否装入，此时容量为M的背包的最大价值0 1 2 3

5、4 5 6000000001051015252530200101520303530001520253040000202530此程序运行结果为35。复杂度分析：程序需要求解N*M个状态，每一个状态需要的时间为O（m/Weighti），所以总的复杂度为O(NM*(M/Weighti)。思考：完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足ci<=cj且wi>=wj，则将物品j去掉，不用考虑。(c=Cost价格，w=Weight重量）即，如果一个物品A是占的地少且价值高，而物品B是占地多，但是价值不怎么高，那么肯定是优先考虑A物品的。TSP问题一、问题描述所谓TSP问题

6、是指旅行商要去n个城市推销商品，其中每个城市到达且仅到达一次，并且要求所走的路程最短（该问题又称货郎担问题、邮递员问题、售货员问题等）。TSP问题最容易想到、也肯定能得到最优解的算法是穷举法，即考察所有可能的行走线路，从中选出最佳的一条。但是用穷举法求解TSP问题的时间复杂性为O(n!)，属于NP问题。请用数学语言对该TSP问题加以抽象，在此基础上给出动态规划求解该问题的递推公式。要求对所给公式中的符号意义加以详细说明，并简述算法求解步骤。用一种你熟悉的程序设计语言加以实现。二、基本思路Length（总回路）= Length（S0S1）+Length（S1S2S3S0）把问题简化：把求通过各点

7、的一条最短的回路 求解从某个（任意）确定点到回路最后一个点的最短路径。规范化公式：d（i，V）表示从i点经过点集V各点一次之后回到出发点的最短距离d（i，V）= minCik + d(k,V k)d（k，）= Cik （其中，Cik表示ik的距离）举例：node 0 1 2 3 0 5 3 2 1 5 7 9 2 3 7 12 3 2 9 12 i/Vj 1 2 3 1,2 1,3 2,3 1,2,3 0 211 5 10 11 212 3 12 14 183 2 14 15 19三、算法伪代码for (i =1;i<n;i+) /初始化第0列 di0=ci0;for( j=1;j<

8、;2(n-1)-1;j+) for(i=1 ; i<n ;i+) if(子集Vj中不包含i) 对Vj中的每个元素k，计算diVj = mincik + dkVj-k | 每一个kVj; 对V2(n-1)-1中的每个元素k,计算: d02(n-1)-1 = minc0k + dk2(n-1)-2; 输出最短路径:d02(n-1)-1; 广义背包问题源代码：#include <iostream>#include <vector>#include <assert.h>#include <windows.h>#include <stdio.h

9、>#include <windef.h>#include <iostream>#include <assert.h>using namespace std;/*fim:前i件物品放入背包容量为m的背包获得的最大收益fim = max(fi - 1m,fi - 1m - k * Wi + k * Vi,其中 1<=k<= m/Wi)边界条件f0m = 0;fm0 = 0;*/const int N = 4;/四种物品const int M = 6;/背包的容积为6int weightN + 1 = 0, 1, 2, 3 ,4;/四种物品的重量

10、分别为1,2,3,4int ValueN + 1 = 0, 5, 10, 15,25 ;/四种物品的价值分别为5,10,20,25int fN + 1M + 1 = 0 ;/fim初始化为零int Completeknapsack()/边界条件for (int i = 0; i <= N; i+)fi0 = 0;for (int m = 0; m <= M; m+)f0m = 0;/递推for ( i = 1; i <= N; i+)for ( m = 1; m <= M; m+)fim = 0;int nCount = m / weighti;/背包最多能装入的同种物品数量for (int k = 0