A SIMPLE 0.5-BOUNDED GREEDY ALGORITHM FOR THE 0/1 KNAPSACK-PROBLEM

被引：6

作者：

SARKAR, UK ^{[1
]}

CHAKRABARTI, PP ^{[1
]}

GHOSE, S ^{[1
]}

DESARKAR, SC ^{[1
]}

机构：

[1] INDIAN INST TECHNOL,DEPT COMP SCI & ENGN,KHARAGPUR 721302,W BENGAL,INDIA

来源：

INFORMATION PROCESSING LETTERS | 1992年 / 42卷 / 03期

关键词：

GREEDY ALGORITHM; APPROXIMATION ALGORITHM; 0/1 KNAPSACK PROBLEM; NON-INCREASING 1ST FIT; ALGORITHMS;

D O I：

10.1016/0020-0190(92)90143-J

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Non-Increasing First Fit (NIFF) greedy algorithm for the 0/1 knapsack problem does not provide a bounded solution. In this paper a simple modification of this greedy procedure is proposed whose solution is no worse than the solution found by the NIFF algorithm and is guaranteed to be 0.5-bounded. A further modification of the proposed algorithm is shown to improve the bound to 1/3 for the special case of the problem when profit per unit weight is the same for all objects. The bounds obtained are shown to be tight. Experiments were performed with random instances of the problem in order to compare the quality of the solution of this algorithm and that of the NIFF algorithm relative to the optimal solution.

引用

页码：173 / 177

页数：5