Knapsack Tak Terbatas dan Coin Change II
Izinkan item digunakan kembali dengan mengiterasi kapasitas ke arah maju, lalu selesaikan coin-change-II (menghitung cara) dan pemotongan batang menggunakan variasi ini
Knapsack Tak Terbatas dan Coin Change II adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Konsep Ransel Tak Terbatas
Dalam Ransel Tak Terbatas, setiap barang dapat diambil berapa pun kali (berbeda dengan ransel 0/1, yang setiap barang digunakan paling banyak satu kali). Definisi keadaannya sama — dp[c] = nilai maksimum yang dapat dicapai dengan kapasitas c — tetapi arah iterasinya berubah. Karena barang dapat digunakan kembali, ketika kita memperbarui dp[c] kita ingin mengizinkan barang saat ini digunakan lagi, sehingga kita mengiterasi kapasitas dari kiri ke kanan (maju).
Iterasi Maju Memungkinkan Penggunaan Kembali
Ingat bahwa dalam ransel 0/1 kita mengiterasi dari kanan ke kiri untuk mencegah penggunaan kembali. Dalam ransel tak terbatas, kita melakukan kebalikannya: mengiterasi dari kiri ke kanan. Saat menghitung dp[c], dp[c-w] sudah diperbarui dalam lintasan saat ini — artinya barang i mungkin sudah disertakan. Inilah yang kita inginkan: barang i dapat ditambahkan lagi ke solusi yang sudah memuat barang i.
def unbounded_knapsack(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(w, W + 1): # iterate LEFT TO RIGHT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(unbounded_knapsack(weights, values, 7)) # 9Penukaran Koin II: Menghitung Cara
Penukaran Koin II menanyakan: jika diberikan pecahan-pecahan koin dan suatu jumlah, berapa banyak cara berbeda untuk membentuk jumlah tersebut (setiap koin dapat digunakan tanpa batas). Ini adalah varian ransel tak terbatas yang, alih-alih memaksimalkan nilai, menghitung combinations. Definisikan dp[c] sebagai banyaknya cara untuk membentuk jumlah c. Kasus dasar: dp[0] = 1 (satu cara untuk membentuk 0: tidak mengambil apa pun).
Implementasi Penukaran Koin II
Untuk setiap koin, iterasikan jumlah dari kiri ke kanan dan akumulasikan: dp[c] += dp[c - coin]. Kasus dasar dp[0] = 1 menjadi dasar penghitungan. Perhatikan bahwa perulangan luarnya adalah perulangan koin dan perulangan dalamnya adalah perulangan jumlah — hal ini secara alami menghasilkan hitungan kombinasi (bukan permutasi), karena setiap pecahan koin dipertimbangkan tepat satu kali sebagai lintasan luar.
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
print(change(5, [1, 2, 5])) # 4
print(change(3, [2])) # 0
print(change(10, [10])) # 1Kombinasi vs Permutasi
Urutan perulangan sangat penting. Jika kita menempatkan jumlah di perulangan luar dan koin di perulangan dalam, kita menghitung permutations (urutan berpengaruh). Untuk jumlah=5 dengan koin [1,2]: 1+2+2 dan 2+1+2 dihitung secara terpisah. Jika kita menempatkan koin di perulangan luar, kita menghitung combinations (urutan tidak berpengaruh): 1+2+2 dan 2+1+2 dianggap sama. Penukaran Koin II meminta combinations, jadi koin menjadi perulangan luar.
# Count COMBINATIONS (order does not matter) — coin outer loop
def combinations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins: # coin outer
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
# Count PERMUTATIONS (order matters) — amount outer loop
def permutations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for c in range(1, amount + 1): # amount outer
for coin in coins:
if c >= coin:
dp[c] += dp[c - coin]
return dp[amount]
print(combinations(5, [1,2,5])) # 4
print(permutations(5, [1,2,5])) # 13Masalah Pemotongan Batang
Masalah ransel tak terbatas klasik lainnya: diberikan batang dengan panjang n dan harga untuk setiap panjang batang 1 hingga n, temukan pendapatan maksimum dengan memotong batang secara optimal. Setiap potongan dengan panjang l dapat dijual seharga price[l], dan potongan dapat digunakan kembali (batang dapat dipotong menjadi beberapa potongan dengan panjang yang sama). Masalah ini langsung dipetakan ke ransel tak terbatas dengan W = n dan barang berupa berbagai panjang potongan.
def rod_cutting(prices, n):
# prices[i] = price of rod of length i+1
dp = [0] * (n + 1)
for length in range(1, n + 1): # each cut length
price = prices[length - 1]
for c in range(length, n + 1):
dp[c] = max(dp[c], dp[c - length] + price)
return dp[n]
prices = [1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting(prices, 8)) # 22Penukaran Koin I: Jumlah Koin Minimum
Penukaran Koin I (masalah yang berbeda) meminta jumlah koin minimum untuk membentuk jumlah target. Di sini dp[c] = jumlah koin minimum untuk membentuk jumlah c. Relasi rekurensinya: dp[c] = min(dp[c], dp[c - coin] + 1). Inisialisasikan semua entri dengan inf, kecuali dp[0] = 0. Ini juga bersifat tak terbatas (koin dapat digunakan kembali), jadi iterasikan dari kiri ke kanan. Kembalikan dp[amount] jika nilainya berhingga, jika tidak, kembalikan -1.
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] = min(dp[c], dp[c - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coinChange([1,5,6,9], 11)) # 2 (5+6 or other combos)
print(coinChange([2], 3)) # -1Perbedaan Utama: Maksimum vs Minimum vs Hitungan
Tiga varian ransel tak terbatas menggunakan operasi yang berbeda pada dp[c-coin]: Maksimalkan nilai: dp[c] = max(dp[c], dp[c-w] + v); inisialisasi dengan 0. Minimalkan biaya: dp[c] = min(dp[c], dp[c-coin] + 1); inisialisasi dengan inf, dp[0]=0. Hitung cara: dp[c] += dp[c-coin]; inisialisasi dengan 0, dp[0]=1. Mengenali varian yang berlaku merupakan separuh tantangan dalam soal wawancara.
Kompleksitas dan Tips Wawancara
Semua varian ransel tak terbatas berjalan dalam waktu O(n × W) dan ruang O(W), dengan n sebagai jumlah jenis barang dan W sebagai jumlah target. Untuk soal koin, n adalah jumlah pecahan koin. Dalam wawancara, nyatakan variannya (maksimum/minimum/hitungan), tulis DP 1D, dan jelaskan secara eksplisit apakah perulangan luar adalah koin atau jumlah — pewawancara mengetahui bahwa perbedaan ini menguji pemahaman DP yang mendalam.
Mengidentifikasi Ransel Tak Terbatas vs 0/1
Gunakan petunjuk berikut untuk mengidentifikasi varian yang berlaku: penggunaan kembali tanpa batas → tak terbatas (iterasi maju); setiap barang tepat satu kali → 0/1 (iterasi mundur); soal menyatakan 'berapa pun kali', 'persediaan tak terbatas', atau 'penggunaan kembali diizinkan' → tak terbatas. Contoh: penukaran koin, pemotongan batang, pemecahan bilangan bulat — semuanya tak terbatas. Jumlah himpunan bagian, partisi, ransel 0/1 — 0/1. Kesalahan ini menyebabkan jawaban yang salah dan sulit diperbaiki.
Pemecahan Bilangan Bulat dan Varian Lain
Pemecahan Bilangan Bulat (LeetCode 343): bagi bilangan bulat n menjadi setidaknya 2 bilangan bulat positif untuk memaksimalkan hasil kalinya. Ini adalah ransel tak terbatas dengan 'barang' berupa bilangan bulat 2 hingga n-1. Definisikan dp[i] = hasil kali maksimum bilangan-bilangan bulat yang jumlahnya i. Untuk setiap barang j dari 2 hingga i, dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Ini menunjukkan bagaimana pola ransel tak terbatas dapat digeneralisasikan melampaui konteks koin.
def integerBreak(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))
return dp[n]
print(integerBreak(10)) # 36 (3+3+4 = 3*3*4 = 36)Uji Cepat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: ransel tak terbatas mengiterasi kapasitas dari kiri ke kanan agar barang dapat digunakan kembali, Penukaran Koin II menghitung combinations dengan menempatkan koin di perulangan luar, dan tiga varian — memaksimalkan, meminimalkan, menghitung — hanya berbeda dalam operasi dan inisialisasi DP. Berikutnya, kita menggunakan ransel 0/1 untuk menyelesaikan Partisi Himpunan Bagian dengan Jumlah Sama.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Knapsack Tak Terbatas dan Coin Change II” gratis?
Ya — teks lengkap “Knapsack Tak Terbatas dan Coin Change II” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Knapsack Tak Terbatas dan Coin Change II”?
Izinkan item digunakan kembali dengan mengiterasi kapasitas ke arah maju, lalu selesaikan coin-change-II (menghitung cara) dan pemotongan batang menggunakan variasi ini Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Knapsack Tak Terbatas dan Coin Change II” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Knapsack 0/1 dan Optimasi Ruang
- Knapsack Tak Terbatas dan Coin Change II
- Jumlah Subhimpunan Sama untuk Partisi
- Jumlah Target dengan Tanda Positif dan Negatif