Program dinamis untuk alokasi anggaran
Isi tabel alokasi dan simpan pilihan terbaik per kapasitas.
dasar #program dinamis
SlideProgram Dinamis 2020 Bagian1Program Dinamis 2020 Bagian2
Yang akan kamu pahami
Definisikan state berdasarkan tahap dan kapasitas, lalu turunkan transisi yang mencakup setiap pilihan.
Konsep inti
State dp[i,b] menyimpan nilai maksimum dari i proyek pertama dengan anggaran b. Untuk proyek yang hanya dapat dipilih sekali, ambil maksimum antara melewatkan proyek dan mengambilnya jika biaya muat. Simpan keputusan per state untuk rekonstruksi pilihan.
Coba langkahnya
A biaya 2 bernilai 4, B biaya 3 bernilai 6, dan C biaya 4 bernilai 7. Anggaran 5.
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| Tanpa proyek | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 4 | 4 | 4 | 4 |
| A,B | · | · | · | · | · | · |
| A,B,C | · | · | · | · | · | · |
Cek pemahaman
Latihan UTS & UAS
- UAS 2026 · No. 4Tulis state, recurrence, dan basis program dinamis.
- UAS 2026 · No. 7Hitung nilai dan pilihan alokasi untuk anggaran terbatas.