Mengajar Pemrograman Anak – Keuntungan Maksimal dari Pemotongan Batang (Knapsack Tanpa Batas) melalui Algoritma Pemrograman Dinamis Top Down

Anda diberikan daftar harga bilangan bulat di mana harga[i] mewakili harga untuk menjual batang ukuran i + 1, dan bilangan bulat n yang mewakili ukuran batang saat ini.

Mengingat Anda dapat memotong batang menjadi sejumlah ukuran yang berbeda, kembalikan keuntungan maksimum yang dapat diperoleh.

Kendala
m = n 1000 dimana m adalah panjang harga.
Contoh 1
Memasukkan
harga = [1, 3, 5, 7, 7, 7]
n = 6
Keluaran
10
Penjelasan
Tabel harga menunjukkan bahwa kita dapat:
Jual tongkat ukuran 1 dengan harga 1
Jual tongkat ukuran 2 harga 3
Jual tongkat ukuran 3 harga 5
Jual tongkat ukuran 4 harga 7
Jual tongkat ukuran 5 harga 7
Jual tongkat ukuran 6 harga 7
Cara optimal untuk memotong batang adalah dengan membaginya menjadi 2 bagian dengan panjang 3, untuk mencapai keuntungan 10.

Keuntungan Maksimal dari Pemotongan Batang (Knapsack Tanpa Batas) melalui Algoritma Pemrograman Dinamis Top Down

Kami membiarkan mewakili keuntungan maksimal untuk batang ukuran-n. Kita dapat mencari potongan pertama i yang dapat berkisar dari 0 hingga n-1 (dengan demikian ukurannya adalah i+1). Ukuran yang tersisa adalah n-1-i dan kita dapat menyelesaikan ini secara rekursif (karena ini adalah input yang lebih kecil). Keuntungan dari potongan pertama adalah harga[i] dan kita dapat membandingkan dan menyimpan keuntungan maksimal dari pemotongan N tersebut.

Rekursi dengan Memoisasi adalah Pemrograman Dinamis Top Down. Dan ini juga dapat dilihat sebagai masalah knapsack tak terbatas di mana knapsack memiliki kapasitas N, dan kita memiliki item berukuran 1, 2, 3, … N dan nilainya diketahui. Kami ingin mengemas knapsack di mana setiap item dapat kami pilih sebanyak yang kami inginkan. Targetnya adalah memaksimalkan nilai knapsack.

Persamaan Pemrograman Dinamis adalah:

tex_c6a598664d6740124dda131595159630 Mengajar Pemrograman Anak - Keuntungan Maksimal dari Pemotongan Batang (Knapsack Tanpa Batas) melalui Algoritma Algoritma Pemrograman Dinamis Top Down, pemrograman dinamis python, mengajar pemrograman anak-anak, video youtube di mana tex_37b93a4d0c412f1c44f88cc3bcb41359 Mengajar Pemrograman Anak - Keuntungan Maksimal Pemotongan Batang (Knapsack Tanpa Batas) melalui Algoritma Algoritma Pemrograman Dinamis Top Down

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices, n):        
        @cache
        def f(n):
            if n<= 0:
                return 0
            ans = 0
            for i in range(n):
                ans = max(ans, f(n- i - 1) + prices[i])
            return ans
        return f(n)
class Solution:
    def maxProfit(self, prices, n):        
        @cache
        def f(n):
            if n<= 0:
                return 0
            ans = 0
            for i in range(n):
                ans = max(ans, f(n- i - 1) + prices[i])
            return ans
        return f(n)

Kami menggunakan @cache untuk membiarkan komputer menyimpan nilai untuk kami. Kompleksitas waktu adalah O(N^2) kuadrat (misalnya waktu polinomial) karena untuk setiap nilai f(N) kita perlu mengulangi N kali. Dan kompleksitas ruang adalah O(N) karena ada paling banyak nilai N untuk disimpan.

–EOF (Blog Komputasi & Teknologi Terbaik) —

Peringkat Bintang GD
Memuat…

674 kata
Postingan terakhir: Teaching Kids Programming – Split Tree untuk Memaksimalkan Produk (Algoritma Pencarian Pertama Kedalaman Rekursif)