Modeling And Solving Of The Extended Discount Knapsack Problem

The extended discounted 0-1 knapsack problem(SD {0-1} KP)is proposed based on the discounted 0-1 knapsack problem(D {0-1} KP),which focuses on describing various problems in commodity promotion.From the scale of the model,there are few items in the itemset of discount 0-1 knapsack problem,which can not be reasonably expressed when describing many practical problems.Therefore,the model needs to be extended and integrated to increase the diversity of discounts when purchasing goods.However,in the process of solving the problem,it is easy to appear abnormal coding probability is too high,premature and solving speed is slow.In view of this phenomenon,this paper discusses some existing knapsack problems based on SD {0-1}KP model and greedy optimization repair strategy in the aspects of model establishment,solution accuracy and coding method.1.Aiming at the existing extended discount 0-1 knapsack problem,a new model is proposed,which increases the number of items in the item set to three.The selection of items in the item set is encoded by triples,and the extended SD {0-1} KP model is established,which is solved by genetic algorithm.In order to improve the efficiency of the algorithm,greedy repair strategy is added.In order to test the effectiveness of the algorithm,test cases are constructed randomly,and the time complexity is significantly reduced by comparing the solution results with the accurate algorithm results.It is concluded that the genetic algorithm with greedy strategy has a significant effect in solving the extended SD {0-1} KP model.2.This paper continues to discuss the existing extended discount 0-1 knapsack problem,proposes the fusion model of discount knapsack and bounded knapsack problem,constructs the bounded discount knapsack problem model,adopts integer coding method to code,and chooses particle swarm optimization algorithm to solve the model.In order to enhance the optimization ability of the particle swarm optimization algorithm,the greedy repair strategy is added,and the results are compared with other algorithms with strong optimization ability.Finally,it is concluded that the particle swarm optimization algorithm with the greedy strategy is better in solving the bounded discount knapsack problem.In order to verify the feasibility of the proposed algorithm,the experimental results of three kinds of bounded discount knapsack problems are compared with the results of the exact solution algorithm,and the results show that the proposed algorithm works well.