A Research on the Efficient Computation of Knapsack Problem
This paper computes the Reasonable Computing Cost Calexact for finding its optimal solution through investigating the tractability of classical knapsack problem 1, and computes the Reasonable Computing Cost Calappx for finding its approximate solution through analyzing the relationship between the variation of computing accuracy and calculated amount of solving knapsack problem instances.The Reasonable Computing Cost is based on the study of the mathematical structure of instances, and integrates many time complexity lower bounds of different algorithms and calculated amount corresponding with instances.After investigating the Reasonable Computing Cost of knapsack problem, we construct the solution scheme for the Efficient Computation with the constraints of users time requirements and computing resources.
Efficient Computation Reasonable Computing Cost Knapsack Problem
Donghai Huang Jinchuan Cui
Institute of Applied Mathematics, Academy of Mathematics and Systems Science Chinese Academy of Sciences, Beijing 100190, China
国际会议
三亚
英文
400-404
2015-12-26（万方平台首次上网日期，不代表论文的发表时间）