Kriftografi - Algoritma Knapsack
· Algoritma Knapsack juga adalah algoritma kriptografi kunci-publik. · Keamanan algoritma ini terletak pada sulitnya memecahkan persoalan knapsack ( Knapsack Problem ). Knapsack artinya karung/kantung. Karung mempunyai kapasitas muat terbatas. Barang-barang dimasukkan ke dalam karung hanya sampai batas kapasitas maksimum karung saja. Knapsack Problem : Diberikan bobot knapsack adalah M . Diketahui n buah objek yang masing-masing bobotnya adalah w 1 , w 2 , …, w n . Tentukan nilai b i sedemikian sehingga M = b 1 w 1 + b 2 w 2 + … + b n w n (16.1) yang dalam hal ini, b i bernilai 0 atau 1. Jika b i = 1, berarti objek i dimasukkan ke dalam knapsack , sebaliknya jika b i = 0, objek i tidak dimasukkan. · Dalam teori algoritma, persoalan knapsack termasuk ke dalam kelompok NP-complete . Persoalan yang termasuk NP-complete tidak dapat dipecahkan dalam orde waktu polinomial.