Materi
Kamus algoritma NIST mendefinisikan masalah knapsack sebagai memilih himpunan barang bernilai terbesar yang muat di sebuah wadah berkapasitas tetap: setiap barang punya nilai dan berat positif, dan setiap barang diambil (1) atau tidak (0). Karena itu namanya juga knapsack 0-1. Panduan pengguna SciPy menyelesaikan soal yang sama dengan milp, seperti di modul ketiga; pelajaran ini memakai cara lain yang tidak butuh solver.
Pemrograman dinamis, menurut NIST, menyelesaikan masalah optimasi dengan menyimpan solusi submasalah (memoisasi) alih-alih menghitungnya ulang. Entri memoization di kamus yang sama memberi contoh Fibonacci: versi naif menghitung nilai yang sama berkali-kali sehingga waktunya tumbuh eksponensial, sedangkan versi yang menyimpan jawabannya jauh lebih cepat. Di Python, penyimpanan itu bisa diserahkan kepada dekorator functools.cache, yang menurut dokumentasinya membungkus fungsi dengan kamus berkunci argumen.
Untuk knapsack, submasalahnya adalah nilai terbaik dengan sebagian barang pertama dan sisa kapasitas tertentu. Nilai itu cukup dihitung dari dua pilihan untuk barang berikutnya: barang tidak diambil, atau barang diambil bila beratnya masih muat, lalu nilainya ditambahkan. Jawaban akhirnya adalah submasalah dengan semua barang dan kapasitas penuh.
from functools import cache
# pecahan uang 1, 4, 5: berapa keping paling sedikit untuk jumlah n?
@cache
def keping(n):
if n == 0:
return 0
return 1 + min(keping(n - p) for p in (1, 4, 5) if p <= n)
print(keping(8)) # 2 (4 + 4), bukan 4 keping hasil ambil-terbesar 5 + 1 + 1 + 1