Pemrograman Dinamis - Berpikir Komputasional | Informatika XI

Summary

This video script delves into the concept of dynamic programming (DP), a computational technique used to solve optimization problems by breaking them into subproblems and storing the results to avoid redundant calculations. The script uses the example of harvesting chili peppers in a grid to illustrate how DP can efficiently find the maximum number of peppers collected, contrasting it with the 3D technique which might not yield the optimal solution. It also touches on the application of DP in everyday life, such as currency exchange, and ends with a reflection on the differences between 3D algorithms and dynamic programming, highlighting their strengths and weaknesses.

Takeaways

• 📚 Dynamic programming (DP) is a method used to solve optimization problems by breaking them down into simpler subproblems.
• 🔍 DP is particularly useful for problems where decisions have consequences on future steps, making traditional techniques like the 3D technique suboptimal.
• 🔑 The two main components of DP are optimization (finding the maximum or minimum value) and the recursive formulation of the problem, where the solution to a larger problem depends on solutions to smaller subproblems.
• 🔄 One of the key challenges in DP is dealing with overlapping subproblems, which can lead to inefficiencies if not handled properly.
• 💡 The technique of memoization is used in DP to store the results of subproblems, preventing the need to recalculate solutions and thus improving efficiency.
• 🌰 The script provides an example of a problem involving harvesting chili peppers arranged in a grid, illustrating how DP can be applied to find the maximum number of peppers that can be collected.
• 🚫 The 3D technique is not suitable for the chili harvesting problem because it does not consider the consequences of choosing one path over another, potentially leading to a non-optimal solution.
• 🔢 The script discusses a numerical example where different paths can lead to different totals of collected peppers, emphasizing the need for a method like DP to find the optimal path.
• 🔄 The process of DP involves filling out a memoization table, starting with the initial conditions and building up to the solution for the entire problem.
• 🎯 The final result of the DP process is the maximum or optimal value for the problem, which, in the case of the chili harvesting example, is the maximum number of peppers that can be collected.
• 🤔 The script concludes with a reflection on the application of DP to real-life problems and a discussion on the differences between the 3D technique and dynamic programming, inviting the audience to consider the strengths and weaknesses of each.

Q & A

What is the main topic discussed in the video script?

The main topic discussed in the video script is Dynamic Programming (DP), a strategy in algorithmic problem-solving, particularly for optimization problems.

What is the difference between Dynamic Programming and the 3D technique mentioned in the script?

Dynamic Programming is a method that solves complex problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations. The 3D technique, which is not fully explained in the script, seems to be an approach that might not always yield optimal solutions, especially when there are overlapping subproblems.

What is the concept of 'memoization' in the context of Dynamic Programming?

Memoization in the context of Dynamic Programming refers to the process of storing the results of expensive function calls and reusing them when the same inputs occur again, thus reducing the computation time by avoiding the need to recompute the same results.

Can you provide an example of a problem solved in the script using Dynamic Programming?

An example provided in the script is about Adria who wants to harvest the maximum number of chili peppers from a grid of plants. The problem is solved using Dynamic Programming by considering the maximum value obtainable from the current box and the optimal values from the boxes above or to the left.

What is the significance of 'subproblems' in Dynamic Programming?

In Dynamic Programming, the significance of subproblems is that they represent smaller, more manageable parts of the main problem. Solving these subproblems and storing their solutions allows for the construction of the solution to the larger problem without redundant calculations.

How does the script illustrate the inefficiency of the 3D technique for the chili harvesting problem?

The script illustrates the inefficiency of the 3D technique by showing that if one starts with the highest value at the bottom-right corner and moves right, there are no other choices for subsequent steps, leading to a suboptimal solution.

What is the role of 'optimization' in the context of the problems discussed in the script?

In the context of the problems discussed, optimization refers to the process of finding the maximum or minimum value, such as the maximum number of chili peppers that can be harvested or the minimum number of steps required to solve a problem.

What is the game described in the script involving Ani and Budi?

The game involves Ani choosing a positive integer 'n', and Budi repeatedly changing 'n' to 1 by applying a series of steps. Budi can replace 'n' with 'n - 1' if 'n' is even, or with 'n / 2' or 'n / 3' if 'n' is divisible by 2 or 3, respectively.

How does the script relate Dynamic Programming to everyday life problems?

The script suggests that Dynamic Programming can be applied to everyday life problems that involve making a series of choices to optimize an outcome, such as the currency exchange problem where one needs to make the best possible change given a limited set of denominations.

What is the final question posed by the script regarding the difference between 3D algorithms and Dynamic Programming?

The script asks for the important differences between 3D algorithms and Dynamic Programming, including their advantages and disadvantages, and which lesson from the topic was the most effective.

Outlines

00:00

🧠 Introduction to Dynamic Programming

This paragraph introduces the concept of dynamic programming (DP) as a strategy for solving computational problems involving optimization. It contrasts DP with the 3D technique, highlighting that DP is more suitable for problems where multiple steps have consequences on subsequent steps. The explanation includes the two main elements of DP: optimization through a series of similar choices, and the recursive formulation of the desired optimal value as a combination of optimal sub-problems. It also touches on the efficiency of DP through memoization, which avoids recalculating solutions for overlapping sub-problems by storing them in a table.

05:03

🌱 Dynamic Programming Example: Adria's Chili Harvest

The second paragraph presents a practical example of applying dynamic programming to optimize the collection of chili peppers in a grid-like arrangement. It explains that using the 3D technique would not yield the optimal solution, as it would lead to suboptimal choices due to the nature of the problem. The paragraph illustrates how to approach the problem using DP, by considering the maximum value that can be obtained from the previous box either above or to the left, and adding the current box's value to find the optimal path for harvesting the maximum number of chili peppers.

10:04

📊 Memoization Table Construction in DP

This paragraph delves deeper into the process of constructing a memoization table for dynamic programming, which is essential for storing the results of sub-problems to prevent redundant calculations. It clarifies the difference between memoization and memorization, emphasizing that memoization specifically refers to saving past computation results in computing. The paragraph provides a step-by-step guide on how to fill out the memoization table, starting with the top-left box and moving right and down, using the values from the辣椒 boxes and the previously calculated values in the table to find the maximum collection of chili peppers.

15:06

🔢 The Number Game: Minimizing Steps to Reach One

The fourth paragraph introduces a number game between Ani and Budi, where the objective is to transform a given positive integer 'n' to the number one through a series of steps. The rules allow Budi to either decrement 'n' by one if it's even or divide it by two, and to divide 'n' by three if it's divisible by three. The paragraph poses a question about determining the minimum number of steps required to reach one, using 25 as an example, and asks for the reflection on the problem-solving process.

20:07

🤔 Reflections on Dynamic Programming and Its Applications

The final paragraph invites reflection on the application of dynamic programming to solve the problem of currency exchange, specifically how to change 15,000 units of currency when only 1,000, 2,000, and 10,000 denominations are available. It questions whether dynamic programming can be applied to this scenario and seeks examples of other everyday problems that can be solved using DP. The paragraph also asks for opinions on the significant differences between the 3D technique and dynamic programming, their advantages and disadvantages, and which lesson from the topic was the most effective. It concludes with a thank you note and encouragement for continued learning.

Keywords

💡Dynamic Programming (DP)

Dynamic Programming is an algorithmic technique used to solve complex problems by breaking them down into simpler subproblems. It is central to the video's theme, which discusses solving optimization problems efficiently. In the script, DP is used to illustrate how to maximize the number of chili peppers harvested by considering overlapping subproblems and avoiding redundant calculations, as seen in the example of Adria picking chili peppers in a grid.

💡Memoization

Memoization is a specific case of caching where the result of expensive function calls are stored to avoid re-calculating them when the same inputs occur again. It is a key concept in the script, used to explain how to efficiently implement dynamic programming by storing the solutions of subproblems to prevent redundant calculations, as mentioned in the context of filling the memoization table to solve the chili picking problem.

💡Optimization

Optimization refers to the process of finding the best solution from a set of available choices. It is a fundamental concept in the video, where the goal is to maximize or minimize a certain value, such as the number of chili peppers collected. The script uses optimization to discuss the problem-solving approach of choosing the best path to collect the maximum number of peppers.

💡Subproblem

A subproblem is a smaller instance of the original problem that needs to be solved as part of the dynamic programming approach. The script explains that the main problem is broken down into subproblems which are solved individually, with their solutions combined to solve the larger problem, as in the case of calculating the maximum number of chili peppers that can be collected from a grid.

💡Recursive

Recursive refers to a process that defines a problem in terms of smaller instances of the same problem. In the video, the concept of recursion is used to explain how the solution to the main problem can be expressed as a combination of optimal solutions to the same subproblem but with smaller sizes, as demonstrated in the dynamic programming approach to the chili picking problem.

💡3D Technique

The 3D Technique mentioned in the script is a problem-solving approach that may not yield the optimal solution for certain types of problems. It is contrasted with dynamic programming to illustrate the limitations of the 3D Technique, such as when it cannot consider all possible combinations of steps to solve the chili picking problem optimally.

💡Overlapping Subproblems

Overlapping subproblems occur when multiple subproblems share the same sub-structure and thus can reuse the solutions of smaller instances. The script discusses the importance of overlapping subproblems in dynamic programming, where the memoization technique is used to store and reuse solutions to avoid redundant calculations, as seen in the example of calculating the maximum number of chili peppers.

💡Memoization Table

A memoization table is a data structure used to store the results of expensive function calls and return the cached result when the same inputs occur again. In the script, the memoization table is used to implement the dynamic programming solution for the chili picking problem, where it stores the maximum number of peppers that can be collected up to each cell in the grid.

💡Computational Efficiency

Computational efficiency refers to the effectiveness of an algorithm in terms of the resources it uses, particularly time and space. The script emphasizes the importance of computational efficiency in dynamic programming by using memoization to avoid redundant calculations and thus improve the efficiency of solving the chili picking problem.

💡Bounded Rationality

Although not explicitly mentioned in the script, the concept of bounded rationality is implied when discussing the limitations of the 3D Technique. Bounded rationality refers to the idea that in decision-making, the rationality of individuals is limited by the information they have, the cognitive limitations of their minds, and the finite amount of time they have to make decisions. The script suggests that dynamic programming, with its systematic approach, can overcome some of these limitations by considering all possible combinations of steps.

💡Algorithmic Strategy

An algorithmic strategy refers to a systematic approach to solving a problem using algorithms. The script discusses dynamic programming as an algorithmic strategy that involves breaking down a problem into subproblems, solving each subproblem just once, and storing their solutions - a strategy that is particularly effective for optimization problems with overlapping subproblems and optimal substructure.

Highlights

Introduction to dynamic programming as a computational strategy in informatics for solving optimization problems.

Explanation of dynamic programming's two main elements: optimization through a series of similar choices and the recursive expression of the desired optimal value.

Discussion on the inefficiency of the 3D technique for certain problems and the suitability of dynamic programming in such cases.

The concept of overlapping subproblems in dynamic programming and the need for an efficient calculation method to avoid redundant computations.

Introduction to memoization as a technique to store solutions of subproblems to improve computational efficiency.

Illustration of a problem involving harvesting chili peppers in a grid, demonstrating the application of dynamic programming.

The process of calculating the maximum number of chili peppers Adria can collect using dynamic programming.

Comparison between the 3D technique and dynamic programming, highlighting the limitations and advantages of each.

The importance of memoization in avoiding unnecessary recalculations and its role in computational efficiency.

A detailed example of filling out a memoization table to solve the chili harvesting problem optimally.

The final result of the memoization table, showing the maximum total number of chili peppers that can be collected.

Introduction to a numerical game between Ani and Budi, involving dynamic programming to determine the minimum number of steps to reduce a number to one.

The rules of the game, where Budi can change the number based on whether it is even or divisible by three.

A practical example of the game, starting with the number 5, and the steps Budi takes to reduce it to one.

A challenge posed to the audience to determine the minimum number of steps required if Ani chooses n = 25.

Reflection on the application of dynamic programming in currency exchange problems, specifically with limited available denominations.

Discussion on the potential of dynamic programming to solve everyday life problems and the concept of memoization in various contexts.

A question posed to the audience about the significant differences between the 3D technique and dynamic programming, including their advantages and disadvantages.

A conclusion summarizing the importance of dynamic programming in computational thinking and its applications in algorithmic strategies.

Transcripts

[Musik]

Assalamualaikum warahmatullahi

wabarakatuh kembali lagi di pelajaran

Informatika kelas 11 masih di materi

strategi algoritmik dan pemrograman

berpikir komputasional pada subbab

pemrograman dinamis

saat menyelesaikan sebuah permasalahan

optimasi yaitu mencari nilai terbesar

atau terkecil Terkadang kita harus

memperhitungkan beberapa kemungkinan

pengambilan langkah untuk menyelesaikan

permasalahan tersebut

kemungkinan-kemungkinan tersebut mungkin

memiliki akibat atau konsekuensi

terhadap langkah-langkah selanjutnya

sehingga pendekatan seperti Teknik 3D

mungkin tidak akan menghasilkan jawaban

yang optimal dalam hal ini teknik

pemrograman dinamis atau Dynamic

programming atau DP mungkin akan lebih

sesuai diterapkan teknik DP mengandung

dua unsur utama yaitu yang pertama

optimasi atau mencari nilai terkecil

atau terbesar melalui serangkaian

pilihan

serupa dengan Teknik 3D kita harus

menentukan rangkaian Langkah apa yang

akan menghasilkan nilai optimal di akhir

namun beberapa dengan permasalahan yang

dapat diselesaikan dengan Teknik 3D

permasalahan yang sesuai untuk teknik GP

memiliki struktur sedemikian rupa

sehingga pilihan langkah terbaik saat

ini belum tentu merupakan pilihan

terbaik secara keseluruhan

sehingga prinsip Bride belum tentu dapat

diterapkan dan semua kemungkinan

kombinasi pilihan langkah harus

diperhitungkan

yang kedua nilai optimal yang diinginkan

untuk permasalahan tersebut biasanya

dapat dinyatakan sebagai kombinasi

optimal dari sub permasalahan yang sama

tetapi dengan ukuran yang lebih kecil

atau dengan kata lain dapat dinyatakan

secara rekursif

namun sub permasalahan yang harus

dipertimbangkan biasanya memiliki

overlap atau persinggungan Sehingga

dalam proses perhitungannya diperlukan

cara yang efisien untuk menghitung

solusi untuk sub permasalahan yang

diperlukan agar tidak terjadi perulangan

atau duplikasi dalam proses perhitungan

cara yang umum digunakan adalah dengan

menyimpan semua solusi dari sub problem

yang sudah diketahui dalam sebuah tempat

penyimpanan atau tabel Teknik ini biasa

disebut dengan teknik memorisasi

[Musik]

contoh

agria ingin memanen tanaman cabai di

halaman rumahnya

tanaman tersebut ditata dalam bentuk

kotak-kotak persegi seperti ilustrasi

pada gambar

angka pada setiap kotak memiliki jumlah

cabai yang ada di masing-masing tanaman

berikut tabelnya

kotak-kotaknya yang sebelah kiri 0

berarti

tidak ada cabainya kemudian sebelah

kanannya ada satu dua tiga itu

melambangkan

cabai yang ada pada tanaman di kotak

tersebut

kemudian di bawahnya ada 10 2 10 5

agria tidak punya banyak waktu karena ia

harus segera pergi ke kampus Oleh karena

itu ia tidak bisa memetik seluruh cabai

tersebut Ia hanya bisa mulai dari kotak

manapun di kolom paling kiri dan

berhenti di kotak manapun di kolom

paling kanan

agria hanya bisa bergerak ke kotak tepat

setelah kanannya atau bawahnya berikut

adalah salah satu dari sekian banyak

kemungkinan jalur yang dapat dilalui

oleh agria untuk memetik cabai pada

gambar agria mulai dari

baris yang ketiga di situ yang berwarna

kuning kemudian bergerak ke kanan

tiga kotak kemudian lanjut ke bawah

Terus lanjut ke kanan dan selesai

pertanyaannya adalah Berapakah jumlah

cabai terbanyak yang bisa dikumpulkan

oleh Adria

berikut jawabannya pertama perlu

dipahami bahwa penggunaan Teknik 3D pada

permasalahan ini tidak akan menghasilkan

jawaban yang benar atau optimal

dapat dilihat bahwa jika kita

menggunakan prinsip 3D maka kita akan

memilih untuk memulai dari kolom pertama

baris terakhir dengan nilai jumlah cabe

terbesar yaitu 20 namun jika kita

memulai dari sini maka tidak ada pilihan

lain untuk langkah-langkah selanjutnya

selain bergerak terus ke kanan maka

nilai total cabe yang akan didapatkan

adalah 20 ditambah 5 ditambah 1 + 0 + 0

sehingga menghasilkan

26 cabai

jelas bahwa ada pilihan-pilihan jalur

lain yang akan menghasilkan total nilai

cabe lebih dari 26

misalnya langkah sebagai berikut akan

menghasilkan jumlah total cabe nol

ditambah 10 tambah 2 tambah 10 tambah 10

tambah 5 sehingga menghasilkan

37 cabai

metode berikutnya yang bisa kita

pikirkan solusinya adalah mencoba semua

kemungkinan jalur lalu menghitung Berapa

nilai total cabai yang bisa didapatkan

dan terakhir mencari nilai terbesarnya

namun dengan metode ini kita menemukan

kendala lainnya yaitu akan ada terlalu

banyak kemungkinan yang harus kita

perhitungkan

satu hal yang dapat kita segera pahami

adalah bahwa ada banyak sekali

persinggungan antara jalur-jalur yang

berbeda sedemikian rupa sehingga akan

ada banyak sekali perulangan yang tidak

perlu ketika kita menghitung nilai total

cabai dari semua kemungkinan jalur yang

ada sebagai contoh kedua jalur di bawah

ini yaitu jalur merah dan jalur biru

akan melalui 4 kotak yang sama dan

menghitung penjumlahan dari nilai di

keempat kotak yang sama tersebut yaitu

pada kotak yang berwarna kuning

misalkan pada jalur biru yaitu dari

kotak pojok kiri atas ke bawah

kemudian ke kanan

empat kali dan

jalur yang berwarna merah dari pojok

kiri atas ke kanan kemudian ke bawah dan

selanjutnya ke kanan tiga kali tentunya

pada jalur merah dan jalur biru

sama-sama melalui jalur yang berwarna

kuning

dengan menggunakan prinsip Dynamic

programming atau DP yang perlu kita

lakukan adalah

pertama-tama menyatakan solusi atau

penyelesaian dari permasalahan awal

sebagai kombinasi dari sub permasalahan

yang lebih kecil

dalam hal ini kita dapat membuat

argumentasi bahwa nilai jumlah cabe

terbanyak yang bisa kita kumpulkan

sampai dengan suatu kotak tertentu

dimanapun kolomnya tergantung dari nilai

terbaik jumlah cabai sampai dengan Kotak

di atasnya atau Kotak di sebelah kirinya

jika ada dan tinggal kita jumlahkan saja

dengan nilai banyaknya cabai di kotak

akhir tersebut

hal ini Tentunya karena kita hanya bisa

bergerak ke kanan atau ke bawah saja

Jika nilai terbaik yang bisa kita

dapatkan akan berakhir pada kotak warna

hitam seperti pada gambar dapat dihitung

dengan cara menghitung nilai terbaik

yang didapatkan sampai dengan Kotak

Merah misalkan nilainya adalah A dan

sampai dengan kotak berwarna biru

misalkan nilainya adalah b maka untuk

mendapatkan nilai terbaik sampai dengan

kotak warna hitam kita hanya mencari

manakah jumlah yang tertinggi antara

nilai a dan b kemudian nilai tersebut

dijumlahkan dengan nilai

C proses di atas mengubah permasalahan

ini menjadi lebih rekursif Dimana kita

bisa menggunakan hasil perhitungan pada

kotak-kotak sebelumnya untuk menghitung

nilai terbaik pada kotak-kotak

selanjutnya yang berada di posisi lebih

ke kanan atau lebih ke bawah

sehingga dengan cara ini kita bisa

menghindari perulangan atau duplikasi

proses perhitungan

proses ini biasanya menggunakan sebuah

tabel perhitungan yang biasa disebut

dengan tabel memoilisasi atau tabel DP

istilah memonilisasi berasal dari bahasa

latin yaitu memorandum yang berarti

mengingat yang kemudian bisa disingkat

sebagai memo dalam bahasa Inggris

mohon dibedakan istilah memoilisasi ini

dengan memorilisasi atau memori season

yang juga memiliki arti yang serupa

yaitu proses pengingat namun memoilisasi

memiliki arti yang khusus dalam dunia

komputasi yaitu menyimpan atau mengingat

hasil perhitungan yang telah dilakukan

sebelumnya sehingga kita perlu mengulang

perhitungan yang sama dua kali

[Musik]

untuk soal ini kita buat tabel

memoilisasi tersebut sebagai berikut

yang pertama kotak paling kiri atas kita

berikan nilai sama dengan nilai kotak

tersebut yaitu nol

Kemudian untuk setiap kotak lainnya

misalkan a adalah nilai yang sudah

dihitung pada tabel memoilisasi untuk

kotak yang ada di atasnya atau 0 Jika

Kotak saat ini ada di baris teratas dan

b adalah nilai yang sudah dihitung pada

tabel memoilisasi untuk kotak yang ada

di sebelah kirinya atau nol jika Kotak

saat ini ada di kolom paling kiri serta

misalkan c adalah nilai cabe yang ada

pada Kotak saat ini maka kita isi Kotak

saat ini pada tabel memoilisasi dengan

nilai maksimal dari a atau b Kemudian

ditambahkan C

langkah berikutnya kita lakukan proses

di atas sampai tabel memoilisasi terisi

penuh sesuai ukuran tabel nilai cabe di

awal nilai paling besar pada tabel

memodifikasi menunjukkan nilai total

jumlah cabai terbesar yang bisa

dikumpulkan

hasil tabel memoilisasi yang sudah

terisi penuh untuk soal di atas adalah

sebagai berikut

tabel di atas adalah kotak tanaman cabai

kemudian tabel di bawah adalah tabel

hasil memoilisasi

pada kotak paling kiri atas yaitu 0

tidak ada cabainya kemudian bergerak

satu kolom ke kanan

menghasilkan satu

kemudian

[Musik]

bergerak satu kolom ke kanan yang ada

isi cabenya yaitu 2

sehingga pada

tabel hasil memoilisasi menghasilkan 3

kemudian

jika ke kanan yang berisi 3 maka di situ

tabel minoisasinya adalah 6 dan jika ke

kanan lagi yang ada cabenya yang berisi

10 maka

tabel memoilisasi menghasilkan 16

kembali ke sebelah kiri lagi pada baris

kedua

di situ ada

cabai yang berisi 10

maka tabel imunisasinya adalah 10 karena

di atasnya adalah nol

kemudian di sebelah kanannya

Masih pada baris kedua

di situ ada

kotak tanaman cabenya adalah

2 HP sehingga pada tabel hasil

memoilisasi adalah 12 kemudian di

sebelah kanannya

otaknya yaitu

ada 10 sehingga pada tabel memoilisasi

adalah 22

kemudian di sebelah kanannya lagi adalah

302 karena 22 ditambah 10 kemudian di

sebelah kanannya adalah hasil tabel

memoilisasinya adalah 37 nah 32 ditambah

332 + 5 = 37

pada baris yang ketiga yaitu

tabel memoilisasi menghasilkan 15

itu dari 10 ya tasnya ditambahkan isi

dari kotak tanaman cabe yaitu 5

kemudian di sebelah kanannya adalah 18

berasal dari 15 ditambah 3 hasilkan 18

kemudian di sebelah kanannya

kotak tanaman cabenya berisi 6 yang kita

tambahkan adalah yang paling banyak

yaitu

22 ditambah 6 sehingga menghasilkan

28 kemudian di sebelah kanannya adalah 5

sehingga menghasilkan tabel momen isasi

adalah 37 karena 32 ditambah 5

kemudian di sebelah kanannya lagi tetap

37 karena kotak tanaman cabenya adalah 0

pada baris yang keempat di situ kotak

tanaman cabenya adalah 0 maka tabel

memorinya adalah 15 kemudian di sebelah

kanannya

dari 15 dan 18 kita pilih 18 yang paling

banyak ditambah 4 sehingga menghasilkan

22 kemudian sebelah kanannya tentunya

kita pilih yang 28 karena lebih banyak

dari 22 sehingga tabel memonya adalah

28 kemudian di sebelah kanannya lagi

menghasilkan

39 yaitu 37 + 2 kemudian di sebelah

kanannya lagi dari 39 dan 37 kita pilih

39 sehingga tabel memorinya adalah 39 +

3 menghasilkan 42

pada baris yang terakhir

di sini hasil tabel memorinya adalah 35

didapat dari 15 + 20 kemudian

di sebelah kanannya

tabel kotak tanamannya adalah 5 kita

pilih

dari 35 dan 22 kita pilih 35 + 5 = 40

kemudian sebelah kanannya adalah 41

yaitu 40 + 1 kemudian sebelah kanannya

lagi yaitu

41 masih tetap kemudian

kotak yang terakhir menghasilkan 42

didapat dari hasil pilihan antara 42 dan

41 kita pilih 42 sehingga tabel

memorinya pada kotak terakhir adalah 402

Ayo berlatih aktivitas bermain angka

selanjutnya deskripsi tugasnya yaitu Ani

dan Budi sedang bermain sebuah permainan

angka pertama Ani akan memilih sebuah

angka bilangan bulat positif n

selanjutnya Budi harus mengubah bilangan

n ini menjadi angka 1 dengan menerapkan

serangkaian langkah sebagai berikut

Budi boleh mengganti bilangan n dengan N

- 1 jika bilangan saat ini adalah genap

atau habis dibagi dua maka Budi boleh

menggantinya dengan n dibagi dua

jika bilangan saat ini habis dibagi 3

maka Budi boleh menggantinya dengan n

dibagi

3

proses ini harus dilakukan oleh Budi

secara terus-menerus sampai bilangan

yang dimilikinya menjadi satu misalnya

Ani Memilih n adalah 5 maka Budi dapat

melakukan Proses mengubah 5 menjadi satu

sebagai berikut dari 5 menjadi 4 menjadi

2 dan menjadi satu di sini kita lihat

ada tiga langkah

pertanyaannya adalah Tentukan Berapa

jumlah langkah minimum yang diperlukan

jika Ani Memilih n = 25

setelah selesai melakukan aktivitas

tersebut jawablah pertanyaan berikut ini

dalam buku refleksi Menurut kalian

apakah permasalahan penukaran uang pada

aktivitas sebelumnya

yaitu menukarkan uang untuk topik

algoritma 3D sebelumnya yaitu pecahan

yang tersedia hanya 1000 2000 dan 10.000

dan kita ingin menukarkan nilai 15.000

Dapatkah diselesaikan dengan teknik

pemrograman dinamis

dan bagaimana caranya

kemudian Apakah ada contoh permasalahan

yang lain dalam kehidupan sehari-hari

yang dapat diselesaikan dengan teknik

pemrograman dinamis atau Setidaknya di

mana teknik memoilisasi dapat diterapkan

[Musik]

kemudian Menurut anda apakah yang

menjadi perbedaan penting antara

algoritma 3 dan pemrograman dinamis

Adakah kekurangan dan kelebihannya

masing-masing

selanjutnya manakah pelajaran yang

paling berkesan dari topik ini

demikian tadi materi pemrograman dinamis

pada bagian berpikir komputersional pada

bab strategi algoritmik dan pemrograman

Terima kasih semoga bermanfaat Selamat

belajar dan tetap semangat

[Musik]