Home // ADVCOMP 2010, The Fourth International Conference on Advanced Engineering Computing and Applications in Sciences // View article

A Novel Local Search Algorithm for Knapsack Problem

Authors:
Mostafa Memariani
Kambiz Shojaee Ghandeshtani
Ahmad Madadi
Mohammad Mohsen Neshati

Keywords: Artificial intelligence; NP-hard; Knapsack problem; Combinational optimization.

Abstract:
Knapsack problem is an integer programming that is generally called "Multidimentional Knapsack". Knapsack problem is known as a NP-hard problem. This paper is an introduction to a new idea for solving one-dimentional knapsack that with defining the "Weight Value Index", "Sorting" and "Smart local search" forms a new algorithm. This algorithm is mathematically formulated and has run on 5 sample problems of one-dimentional knapsack, that in most of them the result is close to the optimum. The results show that this method by comparison with the others recently published in this field, despite of its simplicity, has enough required functionality in order to get the result on the tested items.

Pages: 77 to 80

Copyright: Copyright (c) IARIA, 2010

Publication date: October 25, 2010

Published in: conference

ISSN: 2308-4499

ISBN: 978-1-61208-101-4

Location: Florence, Italy

Dates: from October 25, 2010 to October 30, 2010