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.
Last update:
Last update: 2025-04-04 00:38:30