The Study Of Online Knapsack Problem Under The Special Functions

As a classical problem in combinatorial optimization field,knapsack problem is NP complete problem of combinatorial optimization,and it plays an important role in the field of operations research.With the development of the network,people can observe the change of variables in real time.The invariable decision will not bring benefits to the final income,so the decisions will change with the change of time.Therefore,the research significance of online knapsack problem comes into being.Firstly,this paper presents that there is no constant competition ratio for online knapsack problem,and it is difficult to study this topic.In the study of online knapsack problem,online knapsack model is mainly based on greedy algorithm,and the algorithm in this paper is also based on the improvement of greedy algorithm.The online knapsack problem refers to that the items are given one after another,and the corresponding decision needs to be made when the items are given.Only after the decision is made,the information of the next item will be given.After making the decision to put an item in the knapsack,if the current weight in the backpack exceeds the weight limit,the item in the knapsack needs to be taken out.Once taken out,it can never be put into the knapsack,or if the item is not put into the knapsack,it can never be put into the knapsack again.In this paper,the particularity of function means that the capacity and value of goods meet a corresponding special function model,where the capacity of goods is the independent variable and the value of goods is the function value.Firstly,according to the existing linear function model,the special function model(piecewise linear function)is given,and the constant competition ratio is proved under the special function model,which makes the research of the subject meaningful.Then,it analyzes the models of various special functions,and the algorithm also has a good competition ratio under the general model.When the parameters meet certain conditions,the piecewise linear function model with parameters has a tight competition ratio.Since the convex function model has achieved good results,this paper only extends the piecewise linear function to the concave function model,according to the model of concave function and the greedy algorithm,a good constant competition ratio is obtained for the model of piecewise concave function and convex function.