SOLUSI MASALAH KNAPSACK COLLAPSING DENGAN PENDEKATAN MASALAH KNAPSACK BAKU DAN PROGRAM DINAMIK

Abstract

Masalah knapsack collapsing merupakan generalisasi masalah knapsack 0-1. Kapasitas pada masalah knapsack collapsing merupakan fungsi turun ( non-increasing function ) atas jumlah item yang dimuat. Masalah ini dapat diselesaikan dengan dua pendekatan, yaitu : reduksi ke masalah knapsack 0-1 dan pendekatan program dinamik. Masalah knapsack collapsing dapat diselesaikan dalam waktu pseudo-polinomial dengan kedua algoritma tersebut. Kedua algoritma tersebut akan diimplementasikan ke program dalam bahasa Pascal/C. Data instance yang diberikan akan dijalankan pada kedua program tersebut. Kemudian waktu tempuhnya dicatat. Eksperimen komputasi membuktikan bahwa kedua algoritma tersebut efisien.