Research On The Extended Models And Dynamic Programming Algorithm Of Discounted {0-1} Knapsack Problem

There are many extended models of the knapsack problem,such as the discount{0-1} knapsack problem,the unbounded knapsack problem,the multi-choice knapsack problem,the second knapsack problem,the bounded knapsack problem and the set-union knapsack problem,etc.According to the knapsack type,it can be roughly divided into three categories: single knapsack,multiple knapsack s and knapsacks with restricted items.Obviously,D{0-1}KP belongs to the first type of knapsack problem.As the knapsack problem continues to grow,its application background is also becoming more extensive,so it is becoming more and more important to seek new models and their solving algorithms.Based on the background of real life,this dissertation proposes two extended models of D{0-1}KP and gives their dynamic programming algorithm.The main contents are as follows:The discounted {0-1} knapsack problem with a single continuous variable(D{0-1}KPC)is solved for the problem of capital fluctuations.D{0-1}KPC is an extended model of the discounted {0-1} knapsack problem(D{0-1}KP),which continuously adjusts its knapsack capacity with a continuous variable.In order to solve this model,first of all,we present a varying-capacity discounted {0-1} knapsack problem with real function(D{0-1}KP(?,f)),and advance an exact algorithm(DP-?f-D{0-1}KP)based on dynamic programming.Then,we use the scaling method to transform the continuous variables into discrete variables in D{0-1}KPC,and establish a new discrete mathematical model of D{0-1}KPC.We propose an exact algorithm(DP-D{0-1}KPC)for solving D{0-1}KPC by DP-?f-D{0-1}KP.Given the two instances of D{0-1}KPC,this algorithm can easily get the exact solution.Concern the problem about choosing different production machines and molds for the several types of products,we propose an extended model of the D{0-1}KP,that is,the Discount {0-1} Knapsack Problem with Setup(D{0-1}KPS).D{0-1}KPS refers to the selection of multiple items in the same category,and each category adds an additional fixed setting cost to the objective function and constrains.In order to solve this model,firstly,we analyze the theory of D{0-1}KPS,and construct its sub-model D{0-1}KPS(k,?),then obtain the recurrence formula based on D{0-1}KPS(k,?),and give a dynamic programming algorithm for solving D{0-1}KPS.Concern the structural characteristics about D{0-1}KPS,the modified algorithm merges the idea of non-dominated solution set in multi-objective optimization problem.We make use of the dominant and non-dominated relationships between states to prune the state set at each stage,and a non-dominated state set is formed,thus a modified dynamic programming algorithm is proposed.Finally,given the instance of D{0-1}KPS,the experimental result shows that are two valid and feasible algorithms.