Knapsack dengan Optimasi Ruang

Tabel lengkap membutuhkan memori sebesar n kali cap, yang dapat melonjak pada masukan besar. Optimasi ruang menguranginya menjadi satu baris yang digunakan kembali.

Perhatikan bahwa setiap sel hanya membaca baris sebelumnya, tidak pernah baris yang lebih lama. Jadi, Anda tidak perlu menyimpan seluruh tabel sekaligus.

Simpan satu larik dp dengan panjang cap+1. Saat memproses setiap barang, timpa larik tersebut langsung di tempat agar merepresentasikan baris baru.

Jika Anda menelusuri kapasitas dari kiri ke kanan, dp[w - wt[i]] mungkin sudah diperbarui untuk barang yang sama. Hal itu memungkinkan Anda mengambil barang i dua kali.

Solusinya adalah melakukan perulangan kapasitas dari besar ke kecil. Bergerak mundur menjamin dp[w - wt[i]] masih menyimpan nilai barang pada iterasi sebelumnya.

Saat menghitung dp[w], indeks yang lebih kecil, w - wt[i], masih belum tersentuh pada putaran ini, sehingga tetap merepresentasikan baris di atas seperti yang diharapkan.

Kapasitas di bawah wt[i] tidak dapat memuat barang tersebut, jadi perulangan berhenti pada wt[i]. Melewatkannya menghemat beberapa iterasi yang sebenarnya tidak diperlukan.

Seluruh solusi ini terdiri dari dua perulangan bersarang pada satu larik. Barang di luar, kapasitas mundur di dalam, dan jawaban pun diperoleh.

Setelah semua barang diproses, dp[cap] menyimpan nilai maksimum. Nilainya sama dengan yang diberikan tabel 2D, tetapi dengan penggunaan memori yang jauh lebih kecil.

Anda tidak mempercepat algoritmanya; prosesnya tetap membutuhkan kerja sebanyak n kali cap. Anda hanya mengurangi memori dari kuadratik menjadi linear.

Trik ini menyelamatkan Anda ketika cap besar dan tabel 2D akan melampaui batas memori. Ini adalah teknik andalan kompetisi yang layak dihafalkan.

Uji aturan utama untuk ransel 1D.

Anda telah menyederhanakan tabel 2D menjadi satu larik dan menelusuri kapasitas secara mundur agar tetap benar, dengan menukar memori kuadratik menjadi linear. 🚀