张丹丹，王晓峰,2，冯琬晶，左逢源

(1.北方民族大学 计算机科学与工程学院 宁夏 银川 750021；2.宁夏智能信息与大数据处理重点实验室 宁夏 银川 750021)

0 引言

0-1背包问题(0-1 knapsack problem，0-1 KP)是运筹学中一类重要的组合优化问题，同时也是一类NP难问题，旨在寻求满足背包约束条件下具有最大价值的物品装载方案[1-2]。现实世界中很多复杂问题通过编码都可以转换为背包问题，如工业、经济、金融等方面的资源配置、资金预算、公钥密码系统构建以及装载问题等[3]。0-1背包问题的求解过程本质上为：在不超出背包可装载极限的条件下，选取那些装包比不装包更能使背包获得最大价值的物体。目前求解0-1背包问题的算法很多，除精确算法如回溯法、分支限界法等以外，还有可快速近似求解背包问题的演化算法(evolutionary algorithm，EA)、启发式遗传算法(genetic algorithm，GA)、蚁群优化算法(ant colony optimization, ACO)以及粒子群优化算法(particle swarm optimization，PSO)等[4-7]。但当问题规模较大时，精确算法的求解复杂度是指数函数，而启发式算法求解精确度低。置信传播(belief propagation，BP)算法是一种有效求解组合优化问题的近似算法，可计算边际概率，被广泛应用于人工智能和工程技术的各个方面[8-9]。分析BP算法的原理可以发现，其特征是基于因子图模型的一种消息循环更新算法，该消息可以理解为图上相连两节点之间的一种以概率表示的约束关系。通过某种迭代策略对因子图边上的信息进行传播计算，所有传入节点的信息共同决定该节点传出的信息。信息迭代过程可能收敛到某一组固定点，或可能无限次进行迭代(不收敛)。……