第3章-背包问题课件.ppt

《第3章-背包问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章背包问题问题概述数学模型背包问题（简记KP(KnapsackProblem)）是运筹学、计算机科学中的一个典型优化难题，有着广泛的实际应用背景，如预算控制、项目选择、投资决策、材料切割、货物装载等，并且还常常作为其他问题的子问题被加以研究，一般的整数规划问题都可转为0-1问题或整数背包问题就计算复杂性而言，背包问题是个NP难题，除非P=NP否则不存在多项式时间算法。最常见的背包问题是0-1背包问题，可描述为：给定n个物品和一个背包，每个物品i的重量为wi，价值为pi(i=1,2,…,n),背包能容纳的物品重量为c，且总价值达到最大。在0-1背包问题的基础上，

2、对每种物品选择的数量予以不同限定，或对背包的数量或对背包能放入的物品进行多维限定（如对背包的载重量和容积进行二维限制就变为二维背包问题），就会得出各种类型的背包问题。下面，将给出各种背包问题的数学模型。1.0-1背包问题记pj，wj(j=1,2,…,n)分别为物品的价值和重量，c为背包总重量限制，变量则0-1背包问题模型可写成如下的0-1整数线性规划形式：2.有界背包问题记pj，wj(j=1,2,…,n)分别为第j种物品的价值和重量，第j种物品的数量共有mj个，c为背包总重量限制，此时的背包问题为有界背包问题，即每一种物品装入到背包的数量上界为mj个，其数学模型为

3、：有界背包问题可以转换为0-1背包问题，但转换后并不能降低问题的求解难度。3.无界背包问题记pj，wj(j=1,2,…,n)分别为第j种物品的价值和重量，第j种物品的数量没有限制，即第j种物品的数量在理论上没有限制，c为背包总重量限制，此时的背包问题为无界背包问题，其数学模型如下：虽然第j种物品的数量在理论上没有限制，但实际上由于背包总重量限制为c，因此实际上第j种物品的装入数量最多为：由此可看出，无界背包问题可以转换为有界背包问题，又由于有界背包问题可转换为0-1背包问题，因此无界背包问题也可转换为0-1背包问题。4.多维背包问题前面介绍的背包问题中，物品装入到

4、背包中时，背包都只有一个限制（如装入到背包中的物品总重量不能超过背包的总载重量），这种背包问题称为一维背包问题。若物品装入到背包中时，背包有多个限制就称为多维背包问题，又称多约束背包问题。比如，对背包的载重量和容积进行二维限制就变为二维背包问题，设背包有d个限制，其限制量分别c1,c2,…,cd记pj(j=1,2,…,n)分别为第j种物品的价值wij(i=1,2,…,d;j=1,2,…,n)分别为第j种物品的第i维属性的重量，则其数学模型为：5.多背包问题若存在多个背包问题且可以把物品装入到不同的背包中，这就是多背包问题。多背包问题中的物品数量可以是0-1、有界、

5、无界等各种情况，下面给出每个物品数量是0或1的多背包问题数学模型。记pj，wj(j=1,2,…,n)分别为物品的价值和重量第j种物品数为1，共有m个背包，ci为第i个背包的总重量限制，每个物品可装入任一背包内，变量为则多背包问题的模型可写成如下形式：6.子集和问题在0-1背包问题中，令pj=wj(j=1,2,…,n)，就得到子集和问题，其数学模型为：常用求解技术常用的背包问题经典求解技术（不含启发式算法）主要有以下几种。（1）分支定界法：通过分支来达到把问题所有可能分成各种情况，通过计算整个问题的下界和各种分支情况的上界来达到剪支（对目标最大化问题来说，当一种分支

6、情况的上界小于整个问题的下界时就把这个分支减掉）的目的，从而减少搜索空间，获得最优解得一种搜索方法。对于没有一般性好解法的多种问题，分支定界法是用途很广泛的搜索方法，但不同问题的具体实现各异，技巧性较强。（2）近似算法：给出一个算法并通过数学手段证明该算法的近似比为δ，从而得出该近似比下的近似算法。（3）动态规划法：将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段。一般来说，子问题的重叠关系表现为对给定问题求解的递推关系（也就是动态规划函数），对子问题求解一次病将解填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解，从而避免

7、了大量重复计算。（4）降阶法（或归约法）：通过数学论证将问题实例中的部分变量固定在某一个值，如0-1背包可以通过论证确定某些物品一定要装入到背包中才能取得最优解，而某些物品一定不能装入到背包中才能取得最优解，以此达到减小问题规模的目的，再结合其他方法对已经降阶后的规模更小的数据实例进行求解。数据实例分类为测试背包算法的性能，需要对算法进行测试，测试数据可以由计算机按某种规则自动生成。一般把所有物品的重量限定在[1,R]之内，其中，R为正整数生成数据时，在[1,R]内随机取一个整数作为物品j的重量wj,然后确定数据的类型，每种数据类型对应一个函数f(wj)，最后根据

8、pj=f(