| Knapsack problem is a classic problem in combinatorial optimization,which has important applications in the business,combinatorial mathematics,cryptography,and applied mathematics.The model of knapsack problem is given a fixed capacity knapsack and a series of items,each item has its own size and weight.The target is to maximize the total profit of items in the knapsack under the capacity constraint of the knapsack.The classical knapsack problem is an offline problem,that means the information of each item has been given at the beginning.On the contrary,we study the online knapsack problem in this paper,in which each item is coming one by one in sequence,and we can not know the information of the next item before a decision made on the current item.For online knapsack problem,some previous studies have been done,but no one has studied the online knapsack problem under concave functions before.In this paper,the research is studied under concave functions,that means,for each item with size x,its profit is the corresponding function value f(x).So it is different from the online knapsack problem under convex functions,in which the items are associated with a convex size-profit function.The main work of this paper is as follows.First,based on the research on other knapsack problems,and combining the properties of concave functions,we prove the lower bound of the competitive ratio of this problem;and then we design a good algorithm which can solve the online knapsack problem under concave functions with a good competitive ratio.In this paper,we first study the online knapsack problem under concave functions and get some pioneering results.First,the lower bound of the competitive ratio of online knapsack problem under concave functions given in this paper shows how best the online algorithm can do.Second,the quality of the decision made by the online algorithm in this paper is bounded,that means the difference between the online algorithm results and OPT results is limited. |
PDF Full Text Request