- Sedang diisi
- Dibaca
- Jawaban
Masalah knapsack
Anda hanya bisa membawa beban terbatas, dan setiap barang punya bobot dan nilai. Barang mana yang Anda ambil agar nilai yang dibawa paling besar? Mencoba setiap kombinasi membuat pekerjaan berlipat dua untuk setiap barang. Tabel dengan baris barang dan kolom kapasitas menemukan isi tas terbaik satu sel demi satu sel. Ketuk barang untuk memasukkannya ke tas, dan ketuk lagi (di dalam tas atau di rak) untuk mengeluarkannya. Tas terisi menurut bobot, dan kotak-kotak menunjukkan dolar yang Anda masukkan dibandingkan dengan yang terbaik. Tekan Isi terbaik untuk melihat tas terbaik. Di panel, ubah kilogram dan dolar barang, tambah atau hapus barang, dan atur kapasitas tas. Tampilan Tabel menunjukkan cara pemrograman dinamis menemukan tas terbaik: tekan Putar untuk melihat tabel terisi, atau Langkah dan Mundur untuk bergerak satu langkah demi satu langkah, dan seret penggeser langkah untuk melompat ke mana saja. Setiap baris menambahkan satu barang, setiap kolom adalah kapasitas dalam kilogram, dan setiap sel berisi dolar terbanyak yang muat. Saat tabel dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Ketuk kotak barang untuk memasukkannya ke tas, dan lihat tas terisi menurut berat dalam kilogram.
- Coba capai nilai terbaik dalam dolar, atau tekan Isi terbaik untuk melihat isi tas terbaik.
- Buka tampilan Tabel dan tekan Putar untuk melihat setiap sel memilih antara memasukkan dan meninggalkan barang.
Cara kerja tabel
Setiap baris menambahkan satu barang dan setiap kolom adalah kapasitas dari 0 sampai kapasitas tas. Sebuah sel memuat nilai terbesar yang muat dalam kapasitas itu dengan barang-barang sampai barisnya. Tanpa barang baru, nilainya adalah sel di atas. Dengan barang baru, jika muat, nilainya adalah nilai barang ditambah nilai terbaik untuk sisa bobot, yang ada di baris atas, sejauh bobot barang ke kiri. Sel menyimpan yang lebih besar dari keduanya. Baris pertama, tanpa barang, berisi nol semua.
Membaca balik barang
Sel kanan bawah adalah nilai terbaik. Untuk menemukan barangnya, mulai dari sana dan bandingkan dengan sel di atasnya: jika sama, barang terakhir tidak diperlukan; jika lebih besar, barang itu ada di dalam tas, jadi kurangi dengan bobotnya dan pindah ke kolom itu. Naik satu baris setiap kali sampai baris pertama. Aplikasi menampilkan pembacaan balik ini dengan warna oranye dan mencantumkan barang yang dimasukkan di bawah tabel.
Pertanyaan yang sering diajukan
Apa arti 0/1 dalam masalah knapsack 0/1?
Setiap barang dimasukkan sekali atau tidak sama sekali, tidak pernah sebagian dan tidak pernah dua kali. Jika barang bisa dipotong, seperti butir beras, memasukkan dulu barang dengan nilai per bobot terbaik akan optimal; itulah masalah knapsack pecahan (fractional knapsack).
Mengapa tidak memasukkan dulu barang dengan nilai per bobot terbaik?
Karena barang utuh bisa menyisakan celah. Dengan kapasitas 7 dan barang berbobot 1, 3, 4, dan 5 yang bernilai 1, 4, 5, dan 7, nilai per bobot terbaik ada pada barang berbobot 5, yang hanya menyisakan ruang untuk barang berbobot 1, dengan total 8. Barang berbobot 3 dan 4 bersama-sama bernilai 9.
Seberapa cepat algoritma knapsack?
Tabel memiliki (jumlah barang + 1) kali (kapasitas + 1) sel, masing-masing diisi dalam satu langkah. Itu cepat untuk kapasitas kecil, tetapi kapasitas bisa berupa bilangan yang sangat besar, jadi secara umum masalah ini NP-hard; metode tabel ini disebut pseudo-polinomial.
Bisakah barang yang sama dimasukkan dua kali?
Tidak di sini. Dalam masalah knapsack tak terbatas (unbounded), setiap barang boleh diambil berapa kali pun; tabel lalu membaca sel di sebelah kiri pada baris yang sama, bukan baris di atas, seperti di aplikasi penukaran koin.
Apakah ada data yang dikirim ke mana pun?
Tidak. Semuanya dihitung di browser Anda, dan pengaturan terakhir Anda tersimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor