Masalah knapsack
Pendaki dengan batas beban, pencuri dengan karung, perusahaan dengan anggaran dan daftar proyek: semuanya menghadapi pertanyaan yang sama. Apa saja yang harus dimasukkan agar nilainya paling besar tanpa melewati batas? Itulah masalah knapsack, dan pemrograman dinamis menyelesaikannya secara tepat jika bobotnya bilangan bulat yang tidak terlalu besar.
Masalahnya
Ada n barang, masing-masing dengan bobot dan nilai, dan sebuah tas yang memuat bobot paling banyak W. Pilih sekumpulan barang yang total bobotnya paling banyak W dan total nilainya sebesar mungkin. Setiap barang masuk utuh atau tetap di luar, karena itulah disebut masalah knapsack 0/1. Dengan n barang ada 2ⁿ kemungkinan kumpulan, jadi mencoba semuanya segera menjadi mustahil.
Tabelnya
Misalkan best[i][w] adalah nilai terbesar yang muat dalam bobot w dengan hanya memakai i barang pertama. Maka best[0][w] = 0, dan untuk setiap baris berikutnya ada dua pilihan: biarkan barang i di luar, menghasilkan best[i − 1][w], atau, jika bobotnya wᵢ muat, masukkan barang itu, menghasilkan nilainya ditambah best[i − 1][w − wᵢ]. Yang lebih besar adalah best[i][w]. Mengisi tabel baris demi baris membuat kedua sel yang dibutuhkan selalu sudah siap.
Sebuah contoh
Ambil kapasitas 7 dan empat barang dengan bobot 1, 3, 4, dan 5 serta nilai 1, 4, 5, dan 7. Dengan barang pertama saja, setiap kapasitas mulai dari 1 bernilai 1. Setelah barang kedua ditambahkan, kapasitas 4 bisa memuat keduanya dengan nilai 5. Setelah barang ketiga ditambahkan, kapasitas 7 bisa memuat barang 2 dan 3 dengan nilai 9. Barang keempat, berbobot 5 dan bernilai 7, bisa digabung dengan barang 1 menjadi 8 pada kapasitas 6 atau 7, tetapi 9 lebih baik, jadi sel kanan bawah adalah 9: masukkan barang berbobot 3 dan 4.
Seberapa sulit?
Tabel membutuhkan sekitar n·W langkah. Kelihatannya cepat, tetapi W adalah sebuah bilangan, dan bilangan dengan d digit bisa sebesar 10 pangkat d, jadi pekerjaannya tumbuh secara eksponensial terhadap panjang input. Masalah knapsack adalah NP-hard; masalah ini termasuk 21 masalah NP-complete Richard Karp tahun 1972. Dalam praktiknya, tabel, branch and bound, dan skema aproksimasi yang baik menangani kasus nyata yang besar dengan baik.
Sejarah dan kegunaan
Namanya berasal dari matematikawan Tobias Dantzig pada awal abad ke-20, dan putranya, George Dantzig, memberikan metode greedy klasik untuk masalah ini pada tahun 1957. Masalah knapsack muncul dalam penganggaran dan pemilihan portofolio, dalam memotong bahan baku dengan sisa sesedikit mungkin, dalam memuat kargo, bahkan dalam kriptografi kunci publik awal: kriptosistem Merkle–Hellman tahun 1978 dibangun di atas masalah knapsack, dan berhasil dipecahkan beberapa tahun kemudian.
Jelajahi sendiri
Buka aplikasi, beralih ke tampilan Tabel, lalu tekan Langkah. Sel oranye sedang diisi, dan sel biru adalah dua sel yang dibandingkannya: sel tepat di atasnya, dan di baris atas, sel sejauh bobot barang ke kiri. Setelah sel terakhir, pembacaan balik naik dari sudut kanan bawah dengan warna oranye, dan barang yang dimasukkan muncul di bawah tabel.
Pertanyaan yang sering diajukan
Apa bedanya knapsack 0/1, terbatas, dan tak terbatas?
Dalam versi 0/1 setiap barang diambil paling banyak sekali. Dalam versi terbatas setiap barang punya jumlah salinan yang terbatas, dan dalam versi tak terbatas jumlahnya bebas. Tabelnya hanya sedikit berubah di antara ketiganya.
Apakah metode greedy pernah benar untuk knapsack?
Untuk masalah knapsack pecahan, saat barang bisa dibagi, mengambil dulu nilai per bobot terbaik adalah optimal. Untuk barang utuh hasilnya bisa jauh meleset, meskipun yang lebih baik antara hasil greedy dan satu barang paling berharga selalu setidaknya setengah dari nilai terbaik.
Berapa banyak memori yang dibutuhkan tabel?
(n + 1)·(W + 1) sel untuk tabel penuh, yang diperlukan untuk membaca balik barang-barangnya. Jika hanya nilai terbaik yang diinginkan, satu baris berisi W + 1 sel sudah cukup, diisi dari kanan ke kiri.
Apakah knapsack sama dengan subset sum?
Subset sum adalah kasus khusus ketika nilai setiap barang sama dengan bobotnya dan pertanyaannya adalah apakah tas bisa diisi tepat penuh. Masalah ini juga NP-complete dan diselesaikan dengan tabel yang sama jenisnya.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba masalah knapsack