我想知道运筹学中旅行背包问题。谢谢！

Question

我想知道旅行商问题的数学求解过程。谢谢

Answer 1

背包问题是一个非常有名的问题。可以这样叙述如下。假设有 n 件物品，记为 d1,d2,d3,…… dn。对于每一种物品di (1=<i=<n), 它的重量是wi ,而它的价值为 vi。现在要求用这 n 种物品的子集填满背包，使其总重量不超过给定的重量限制 TOT，并使得背包的价值尽可能高。

1.实数背包
物品可以一部分放在背包中，那么直接贪心就行了，把物品按性价比(v[i]/w[i])升序放入即为最优解。
复杂度O(n+nlogn)

2.整数背包
物品只能整个放入背包，不允许拆开放，用动态规划求解。
dp[i,j]表示前i个物品放入容量为j的背包中可以得到的最优解。
状态转移方程：dp[i,j]=max{dp[i-1,j],dp[i-1,j-w[i]]+v[i]}
复杂度O(nm)

3.多重背包
与1、2不同，这里有k个背包，每个背包有不同的容量，其它一样。
没什么好办法，只能搜索。
对于每个物品i，枚举它能被放在背包j，也可以不放物品i。
复杂度O(kn)
可以针对不同的题目采取不同的剪枝。

背包问题数学模型为(由于输入问题,下标很难输入规范,如c1中1是下标,请注意)

maxZ=c1x1+c2x2+...+cnxn
w1x1+w2x2+...+wnxn<=W
xi>=0,且为整数,i=1,2,...,n

式中：
ck为第k种物品的单位价值，wk是第k种物品的单位重量或体积，W是背包的重量或体积限制。

动态规划的有关要素如下:
阶段k：第k次装载第k种物品（k=1,2,…,n）
状态变量sk：第k次装载时背包还可以装载的重量(或体积)
决策变量xk：第k次装载第k种物品的件数
决策允许集合：Dk(sk)={dk|0 xksk/wk，xk为整数}
状态转移方程：sk+1=sk－wkxk
阶段指标：vk=ckxk

一般来说，用来解决背包问题的方法有递归法和贪心法等，但用这两中方法来解决背包问题都有其不可避免的缺点，递归法虽能遍历搜索空间，找到最优解，但由于此问题的解的空间是以2的N级增长的，所以它只适用于解决小规模的背包问题，而贪心法又很难真正找到最优解，此方法找到的最优解往往与真正的最优解相差很远。而遗传算法作为一种随机的优化与搜索方法，具有良好的并行性，而且遗传算法只需利用目标的取值信息,而无需递度等高价值信息,因此适用于任何规模。遗传算法的高度非线形的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性。

（如果你是需要计算机编程序的话，答案内容就更多些，现在不晓得你应用背包问题做什么呢）

Answer 2

8558

Answer 3

ABCD