| Autor: |
Jui-Sheng Chang, Jen-Chun Chang, Hsin-Lung Wu |
| Rok vydání: |
2018 |
| Předmět: |
|
| Zdroj: |
Recent Advances in Intelligent Information Hiding and Multimedia Signal Processing ISBN: 9783030037444 |
| DOI: |
10.1007/978-3-030-03745-1_5 |
| Popis: |
In this paper, we study the d-dimensional knapsack problem (d-KP). The problem d-KP is a generalized version of the well-known knapsack problem (1-KP) which is known to be an NP-complete problem. It is also known that there is no fully polynomial-time approximation scheme for d-KP for \(d >1\) unless \(P=NP\). In this work, we design an approximation algorithm for d-KP based on the Hopfield networks. Experimental results show that our proposed algorithm outperforms a well-known greedy algorithm in many cases. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
