Knapsack Problem (KP) merupakan masalah optimisasi dalam menentukan objekdari sekumpulan objek yang memiliki nilai dan bobot yang akan ditempatkan ke dalam media penyimpanan dengan tujuan memaksimumkan nilai barang dengan syarat kapasitas bobot media penyimpanan terbatas. Dalam tugas akhir ini, akan dibahas {0-1} Knapsack Problem ({0-1} KP) yang direpresentasikan dalam bentuk graf berarah. Setelah direpresentasikan dalam bentuk graf berarah, kemudian dilakukan transformasi pada nilai busur pada graf berarah tersebut dan dicari lintasan terpendek antar dua node. Untuk mencari lintasan terpendek, digunakan Algoritma Amoeboid Organism dengan inputnya adalah matriks adjacency dari graf berarah yang telah ditransformasi nilai busurnya dan matriks konduktivitas. Output dari algoritma ini adalah menghasilkan matriks konduktivitas yang elemen-elemennya bernilai mendekati 0 atau 1. Entri yang bernilai mendekati 1 merepresentasikan lintasan terpendek pada graf. Lintasan terpendek yang diperoleh akan menjadi solusi yang optimal pada {0-1} KP.

---

Knapsack Problem (KP) is optimization problem to choose object from set of objects which have profit and weight and the object will be placed in limited storage with total of profit is maksimum. First, will be explained about representing {0-1} Knapsack Problem ({0-1} KP)to directed graph. After {0-1} KP is represented in directed graph, so transforming value of edge on directed graph and dicari lintasan terpendek antar dua node. To search shortest path, use Amoeboid Organism Algorithm with adjacency matrices from directed graph and conductivity matrices as input. Output from this algorithm is produce conductivity matrices with element which have value approach 0 and . Element which have value approach 1 represent shortest path on graph. Shortest path on graph is optimal solution in {0-1} KP.