基于贪心回溯的求解完全0-1背包问题局部动态规划算法OA北大核心CSTPCD

A local dynamic programming algorithm was proposed based on the greedy and backtracking method for the NP-hard problem of complete 0-1 knapsack.The greedy and backtracking techniques were utilized to quickly find an approximate optimal solution and then the optimal solution was approached through the result of local dynamic programming,balancing the correctness and time complexity of the algorithm.Compared with traditional dynamic programming algorithms,the solution time in most cases was significantly reduced,while compared with intelligent algorithms,it can guarantee the optimal solution.Numerous experimental results show that the proposed algorithm can accurately find the optimal solution in a shorter time in most cases compared to classical dynamic programming algorithms,and the knapsack capacity does not directly affect the solution time.For cases where the knapsack capacity is extremely large,this algorithm can greatly reduce the solution time.