2023年7月29日发(作者：)

维普资讯

第２９卷第１期　温州大学学报・自然科学版　２００８年２月　Ｖｏｌ　２９，Ｎｏ１　Ｊｏｕｒｎａｌ　ｏｆ　Ｗｅｎｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ・Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅｓ　Ｆｅｂ．２０ｏ８　有序组合树法求解Ｏ一１背包问题初探　安晨，付永军　（兰州交通大学交通运输学院，甘肃兰州　７３００７０）　摘要：以０－１背包问题为研究对象，建立教学模型，采用有序组合树法对中小规模的背包问题进行　求解．与传统的贪婪算法相比，该算法更容易找到最优解．并通过实例说明该算法对解决中小规模的　０－１背包问题是行之有效的．　关键词：背包问题；有序组合树；算法　中图分类号：Ｏ２２１，４　文献标识码：Ａ　文章编号：１００６．０３７５（２００８）０１．００１０．０５　背包问题是整数规划中一类较为特殊的问题，是一个经典的ＮＰ一完全问题，也是一个典型的　优化难题，其计算的复杂性为Ｄ（２“）ｎ１．背包问题在现实生活中具有广泛的应用背景，如物流公　司的货物发配问题、集装箱的装运问题以及工厂的下料问题等都可以用背包问题进行求解．解决　背包问题的算法有最优算法和启发式算法，最优算法包括穷举法、动态规划法、隐数法以及有序　组合树法　等，启发式算法包括贪婪算法、遗传算法、模拟退火算法以及禁忌搜索算法等一些智　能算法．这些算法各有优缺点，有序组合树法原理简单，操作简便．对许多算例，用有序组合树　法处理，更容易找到最优解，甚至树根即为最优解．　１　Ｏ一１背包问题　给定ｎ件物品和一背包，物品　的价值为ｃ』，体积为　，背包的容积为　，如何选择装入背　包的物品，才能使得装入背包中物品的总价值最大．引入　为一０－１变量，各变量的约束如下：　１ｆ　１，第ｉｏ，第ｉ件物品不装入背包　件物品装入背包　．，　，ｚ，…，　＿ｌ　背包容量约束：　ｘｉＶｉ　Ｖ　ｉ＝１　０一Ｉ背包问题的数学模型如下：　ｍａＸ　Ｚ＝∑　ｃｆ　ｘ／　＝０或Ｉ，ｉ＝Ｉ，２，…，ｎ戤，　，，…，　趴ｔ∑　ｉ＝Ｉ　收稿日期：２００７．０７．０９　作者简介：安晨（１９８３．），女，甘肃庆阳人，硕士研究生，研究方向：交通运输规划与管理