求解0-1背包问题的多种算法策略的分析  

Design and analysis of multiple algorithm strategies for solving 0-1 knapsack problem

作　　者：陈艳 文晓棠 钟广玲 Chen Yan;Wen Xiaotang;Zhong Guangling(School of Data Science,Guangzhou Huashang College,Guangzhou 510520,China)

机构地区：[1]广州华商学院数据科学学院,广州510520

出　　处：《现代计算机》2023年第15期1-9,共9页Modern Computer

基　　金：2019年创强工程/省级一流专业建设——计算机科学与技术。

摘　　要：0-1背包问题是一个经典的组合优化问题,常常被应用于资源分配、物流管理等领域,并且在计算机科学和数学中具有重要的理论价值。解决0-1背包问题有多种策略,常见的策略为动态规划法、回溯法和分支限界法,为了确定对该问题求解的最有效方法,研究三种算法求解的性能表现是十分必要的。通过探讨求解0-1背包问题的三种不同算法,并给出该问题的动态规划法、回溯法和分支限界法的求解思路和算法设计,然后通过实验对比和分析三者的运行时间效率。实验表明,三种算法各具优缺点,要根据问题特点和需求来灵活选择算法。0-1 knapsack problem is a classic combinatorial optimization problem,which is often used in resource allocation,logistics management and other fields,and has important theoretical value in computer science and mathematics.There are many strategies to solve the 0-1 knapsack problem.The common strategies are dynamic programming,backtracking and branch and bound.In order to determine the most effective method for solving this problem,it is necessary to study the performance of the three algorithms.This paper discusses three different algorithms for solving the 0-1 knapsack problem,and gives the solution idea and al-gorithm design of the dynamic programming method,backtracking method and branch and bound method of this problem,and then compares and analyzes the running time efficiency of the three methods through experiments.Experiments have shown that each of the three algorithms has its own advantages and disadvantages,and it is necessary to flexibly select algorithms based on the charac-teristics of the problem and the solving needs.

关 键 词：0-1背包问题 动态规划 回溯法 分支限界法 时间复杂度 

分 类 号：O224[理学—运筹学与控制论]