Algorithms for randomized time-varying knapsack problems

摘要

In this paper, we first give the definition of randomized time-varying knapsack problems () and its mathematic model, and analyze the character about the various forms of . Next, we propose three algorithms for : (1) an exact algorithm with pseudo-polynomial time based on dynamic programming; (2) a 2-approximation algorithm for based on greedy algorithm; (3) a heuristic algorithm by using elitists model based on genetic algorithms. Finally, we advance an evaluation criterion for the algorithm which is used for solving dynamic combinational optimization problems, and analyze the virtue and shortage of three algorithms above by using the criterion. For the given three instances of , the simulation computation results coincide with the theory analysis.