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. 
    
11. def main():
12.     M = 1, 6, 10
13.     N = 12
14.     print(solve(M, N))
15. 
    
16. if __name__ == '__main__':
17.     main()

2. Top-down:

1. def solve(x):
2.     if x == 0: return 0
3. 
   
4.     best = float('inf')
5.     for k in range(len(M)):
6.         if M[k] <= x:
7.             best = min(best, solve(x - M[k]) + 1)
8.     return best
9. 
   
10. def main():
11.     global M
12.     M = 1000, 2000, 5000
13.     N = 12000
14.     print(solve(N))
15. 
    
16. if __name__ == '__main__':
17.     main()

Menghitung Akar Kuadrat Menggunakan Iterasi (Dengan Gambar)

Sedikit Aljabar & Geometri

Bagaimana cara menghitung √10 itu?

Coba lihat gambar berikut:

Pada gambar di atas, luas gabungan dari kotak hitam, merah, dan biru adalah 10, dan luas kotak hitam adalah 9. sedangkan panjang sisi kotak hitam adalah √9 = 3, dan panjang sisi kotak hitam + x adalah √10.

Sekarang, kita perlu menghitung x (karena √10 - √9 = x).

Kita sudah tahu bahwa gabungan dari kotak merah, biru, dan hitam tertumpuk (overlap) dengan kotak hitam, maka total  luas kotak merah dan biru adalah 10 - 9 = 1

luas 1 kotak merah = x ⋅ 3. namun karena jumlah kotak merah adalah 2, maka luas total kotak merah = x ⋅ 3 ⋅ 2.

total luas kotak merah dan biru = x ⋅ 3 ⋅ 2 + x² = 1

1 - x² = x ⋅ 6

x = (1 - x²) ÷ 6

6 = (1 - x ⋅ x) ÷ x

6 = 1 ÷ x - x

x = 1 ÷ (6 + x)

Nah, persamaan ini tidak bisa diselesaikan karena nilai x bergantung dengan angka x itu sendiri(kecuali menggunakan akar-kuadrat. ini tidak bisa karena kita ingin membuat fungsi akar-kuadrat itu sendiri).

 

Maka untuk menghitungnya, kita bisa menggunakan iterasi (iteration).

Kita bisa mensubstitusi sebuah persamaan dengan persamaan itu sendiri.

Coba lihat:

x = 1 ÷ (6 + x)

   = 1 ÷ (6 + (1 ÷ (6 + x)))

   = 1 ÷ (6 + (1 ÷ (6 + (1 ÷ (6 + x)))))

   = 1 ÷ (6 + (1 ÷ (6 + (1 ÷ (6 + (1 ÷ (6 + x)))))))

 

Memprogram iterasi perhitungan √10

Ketika kita menggunakan metode iterasi (untuk menghitung sebuah angka), kita tidak bisa menghitung angka dengan persis, tapi kita bisa menghitung aproksimasi angka. semakin banyak iterasi yang dilakukan, semakin akurat kita dengan angka sebenarnya.

Pada iterasi ke-0, kita bisa mengatur x = 0 (sebagai placeholder):

Iterasi ke-0:

x₀ ≈ 0

Pada iterasi ke-1, baru kita memasukkan persamaan:

Iterasi ke-1:

x₁ ≈ 1 ÷ (6 + x₀) = 1 ÷ 6

Iterasi ke-2:

x₂ ≈ 1 ÷ (6 + x₁) = 1 ÷ (6 + 1 ÷ 6)

Iterasi ke-3:

x₃ ≈ 1 ÷ (6 + x₂) = 1 ÷ (6 + 1 ÷ (6 + 1 ÷ 6))

Perhatikan angka 'kecil'-nya (₀, ₁, ₂, dsb) di variabel x.

Nah sekarang kita bisa membuat program-nya dengan Python.

sqrt_10.py

Membuat List dari Input Files pada Python

 Ada banyak cara utnuk membuat list langsung dari input files seperti: 

Buat list kosong, masukkan satu persatu listnya denagn loop (while atau for), menggunakan listkosong.append(variabelinput). Nah biar bisa berhenti, masukkan len listnya berapa (bisa diinput atau tidak) kalau nggak ada len listkosongnya bisa pake sentinnel (if variabelinput !="Q" or "q") untuk mengatur agar loop sesuai. Seperti:

# creating an empty list
lst = []

# number of elements as input
n = int(input("Enter number of elements : "))

# iterating till the range
for i in range(0, n):
    ele = int(input())

    lst.append(ele) # adding the element
    
print(lst)
 

Bagaimana kalau mau membuat input dalam bentuk list? bisa saja , tapi harus dipisah pake perintah split().Ingat, yang dipisah itu masih variabel string, kalau mau int harus diganti lagi. 

Bisa begini: 

input_string = input('Enter elements of a list separated by space ')
print("\n")
user_list = input_string.split()
# print list
print('list: ', user_list)

# convert each item to int type
for i in range(len(user_list)):
    # convert each item to int type
    user_list[i] = int(user_list[i])

# Calculating the sum of list elements
print("Sum = ", sum(user_list))

Atau : 

# number of elements
n = int(input("Enter number of elements : "))

# Below line read inputs from user using map() function
a = list(map(int,input("\nEnter the numbers : ").strip().split()))[:n]

print("\nList is - ", a)

Sumber:

https://pynative.com/python-accept-list-input-from-user/

https://www.geeksforgeeks.org/python-get-a-list-as-input-from-user/

Nambah Elemen Dalam List (Python)

Ada banyak cara tapi yang cukup mudah adalah dengan append atau extend. Bedanya kalau extend bisa nambah beberapa list sekaligus, kalau append harus satu persatu.  Kalau nambah beberapa elemen dalam append akan dianggap satu list. 

https://stackoverflow.com/questions/252703/what-is-the-difference-between-pythons-list-methods-append-and-extend

 

Kalau ada soal seperti ini (https://www.practicepython.org/exercise/2014/02/15/03-list-less-than-ten.html)

Take a list, say for example this one:

  a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

and write a program that prints out all the elements of the list that are less than 5.

Salah satu solusinya yang pakai append: 

Append juga bisa menambah elemen baru dengan tambahan string seperti di sini:

https://tutorial.eyehunts.com/python/python-add-to-list-in-a-loop-appending-elements-in-list-example-code/

-ww-