Senin, 18 Juli 2022

Dynamic Programming di Python

Ini adalah salah satu materi yang ada di buku Pemrograman Kompetitif. Buku ini bisa di download di https://tlx.toki.id/courses/competitive/chapters/07/lessons/A. Seharusnya penjelasannya diketik ulang , tapi maaf belum sempat... 

Dalam buku dijelaskan konsep dan Pseudocode dari soal. Keduanya diterjemahkan dalam bahasa Python versi saya.

Soalnya seperti ini:

Diberikan M jenis koin, masing-masing jenis bernilai a₁,a₂, ....aₘ rupiah. Asumsikan banyaknya koin  yang ada tak terbatas. Tentukan banyaknya koin paling sedikit untuk membayar tepat sebesar N rupiah!

Solusinya bisa diselesaikan dalam dua cara: Bottom up dan Top down.

1. Bottom-up: (ubah variabel M dan N untuk mengubah input)

  1. def solve(a, N):
  2.     f = [0] * (N + 1)
  3.     for x in range(1, N + 1):
  4.         best = float('inf')
  5.         for k in range(len(a)):
  6.             if a[k] <= x:
  7.                 best = min(best, f[x - a[k]] + 1)
  8.         f[x] = best
  9.     return f[-1]

  10. def main():
  11.     M = 1, 6, 10
  12.     N = 12
  13.     print(solve(M, N))

  14. if __name__ == '__main__':
  15.     main()


2. Top-down:

  1. def solve(x):
  2.     if x == 0: return 0

  3.     best = float('inf')
  4.     for k in range(len(M)):
  5.         if M[k] <= x:
  6.             best = min(best, solve(x - M[k]) + 1)
  7.     return best

  8. def main():
  9.     global M
  10.     M = 1000, 2000, 5000
  11.     N = 12000
  12.     print(solve(N))

  13. if __name__ == '__main__':
  14.     main()

Tidak ada komentar:

Posting Komentar