Knapsack Pecahan Berdasarkan Rasio
Mengambil nilai per bobot tertinggi terlebih dahulu
Knapsack Pecahan Berdasarkan Rasio adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Persiapan Knapsack
Anda memiliki item dengan nilai dan bobot, serta tas dengan kapasitas terbatas. Tujuannya adalah membawa total nilai sebesar mungkin. 🎒
Versi Pecahan Dapat Dibagi
Dalam versi pecahan, Anda boleh mengambil sebagian dari suatu item, seperti setengah karung biji-bijian. Kebebasan inilah yang membuat greedy berhasil di sini.
Nilai per Bobot
Metrik utamanya adalah rasio nilai terhadap bobot setiap item. Rasio tinggi berarti banyak nilai yang dikemas dalam ruang yang sangat kecil.
ratio = value / weightUrutkan Berdasarkan Rasio Terbaik
sort item berdasarkan nilai per bobot, dari yang tertinggi terlebih dahulu. Rencana greedy adalah terus mengambil nilai yang paling padat dari yang tersedia.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Ambil Utuh Selama Masih Muat
Telusuri list yang telah diurutkan dan ambil setiap item secara utuh jika masih muat dalam kapasitas yang tersisa. Tambahkan nilai penuhnya ke total Anda.
if weight <= cap:
total += value
cap -= weightIsi Celah Terakhir
Saat suatu item terlalu besar, ambil pecahan yang tepat memenuhi ruang tersisa. Setelah itu tas penuh dan Anda berhenti.
total += value * (cap / weight)Mengapa Urutan Rasio Berhasil
Setiap unit kapasitas harus memuat nilai sebanyak mungkin, jadi item yang paling padat harus ditempatkan terlebih dahulu. Menggantinya dengan item yang kepadatannya lebih rendah hanya mengurangi nilai.
Ransel 0/1 Itu Berbeda
Jika barang tidak dapat dibagi, pendekatan rakus berdasarkan rasio akan gagal. Versi 0/1 memerlukan pemrograman dinamis, bukan pengurutan sederhana ini.
Waktu Eksekusi
Pengurutan berdasarkan rasio memerlukan O(n log n), dan perulangan pengisian bersifat linear. Itu cukup cepat untuk batasan umum dalam kontes.
Perhatikan Pecahan Terakhir
Gunakan bilangan titik mengambang atau bilangan rasional eksak untuk barang sebagian. Memotong terlalu awal dapat mengurangi nilai dan menyebabkan jawaban salah.
Penerapannya
Bayangkan memuat muatan, mencampur bahan bakar, atau membagi sumber daya. Setiap kali bagian-bagian dapat dibagi, pendekatan rakus berdasarkan rasio adalah alat Anda.
Pemeriksaan Singkat
Anda sedang mengisi tas dalam masalah ransel pecahan.
Ringkasan
Urutkan barang berdasarkan nilai per berat, ambil barang utuh selama masih muat, lalu ambil sebagian barang untuk memenuhi tas. Pendekatan rakus ini optimal hanya jika barang dapat dibagi. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Knapsack Pecahan Berdasarkan Rasio” gratis?
Ya — teks lengkap “Knapsack Pecahan Berdasarkan Rasio” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Knapsack Pecahan Berdasarkan Rasio”?
Mengambil nilai per bobot tertinggi terlebih dahulu Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Knapsack Pecahan Berdasarkan Rasio” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Pola Pikir Greedy
- Pemilihan Aktivitas Berdasarkan Selesai Terawal
- Knapsack Pecahan Berdasarkan Rasio
- Mengenali Saat Greedy Gagal