基于图论求解多选择背包问题

Solution to multiple-choice knapsack problem based on graph theory

多选择背包问题涉及的约束条件种类最多,在背包问题的各种变形中最为复杂。使用动态规划的思想,巧妙地把这个组合优化领域的问题转化成图论上求最短路径的问题。因为标准的Dijkstra算法只能找出两个节点间的一条最短路径,为了克服这个问题,对该算法进行了改进。对案例的测试表明,该算法能成功地算出多选择背包问题的全部最优解。首次把动态规划、图论算法共同应用到多选择背包问题,既能发挥动态规划的理论优势来大大减少计算量,又能充分利用图论的已有成果。

Among variations of Knapsack problem, multiple-choice Knapsack problem （MCKP） is the most complicated, for it is involved in the most types of constraint condition. First, the problem from combinatorial optimization is skillfully transferred to the shortest path problem from graph theory on the basis of dynamic programming. Because the standard Dijkstra algorithm can only fred one shortest path between two vertexes, the algorithm is correspondingly improved. Final, it is tested by the case, and turned out to be able to find all optimal solutions of MCKP. Dynamic programming and graph theory are originally applied to MCKP, which could decrease much amount of computation by the theory of dynamic programming, and could take full advantage of the obtained discoveries of graph theory.