Rod Cutting Problem

Q: Apa kompleksitas waktu dari masalah pemotongan batang?

Tabel membutuhkan waktu O(n²) dan memori O(n): panjang len mencoba len potongan pertama, dengan total n(n+1)/2 percobaan. Tanpa jawaban yang disimpan, rekursi membuat tepat 2^n pemanggilan untuk batang dengan panjang n, karena setiap panjang memanggil semua panjang yang lebih pendek.

Q: Mengapa pemotongan batang merupakan masalah knapsack tanpa batas?

Anggap setiap potongan dengan panjang k sebagai barang dengan bobot k dan nilai prices[k-1] , dengan jumlah yang tidak terbatas, dan batang sebagai tas berkapasitas n yang harus diisi tepat sampai penuh. Jadi, nilai total terbaik dari barang-barang tersebut adalah harga terbaik untuk batang itu.

Q: Bagaimana cara menentukan tempat untuk memotong batang?

Simpan, untuk setiap panjang, potongan pertama k yang menghasilkan harga terbaiknya. Mulai dari panjang n: potong satu bagian dengan panjang yang tersimpan, pindah ke panjang yang tersisa, lalu ulangi hingga mencapai 0. Potongan-potongan tersebut membentuk satu rencana terbaik.

SedangDynamic programming

+10

Kamu memiliki batang dengan panjang n, dengan n = prices.length. Potongan dengan panjang k dijual seharga prices[k-1]. Kamu boleh memotong batang menjadi potongan-potongan dengan panjang bilangan bulat sebanyak yang kamu mau, atau menjualnya utuh. Kembalikan jumlah uang terbanyak yang bisa kamu dapatkan dengan menjual seluruh batang.

Fungsi

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] adalah harga potongan dengan panjang k; panjang batang tersebut adalah prices.length
Mengembalikaninteger: uang terbanyak yang bisa diperoleh seluruh batang

Batasan

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

Contoh

Input: prices = [2, 5, 7, 8]
Output: 10
Penjelasan: Dua potongan dengan panjang 2 dijual seharga 5 + 5 = 10. Menjual batang secara utuh menghasilkan 8, sedangkan satu potongan sepanjang 1 ditambah satu potongan sepanjang 3 menghasilkan 2 + 7 = 9.

Pertanyaan lanjutan

Bagaimana jika kamu boleh memotong batang paling banyak m kali? Apa yang perlu diketahui setiap entri tabel dalam kasus itu?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Sebuah batang dengan panjang n memiliki 2^(n-1) cara untuk dipotong. Kamu tidak perlu mencoba semuanya: apa pun potongan pertamanya, sisanya adalah batang yang lebih pendek dan mengajukan pertanyaan yang sama. Jadi, hanya ada n+1 jawaban, satu untuk setiap panjang, dan menghitungnya mulai dari yang paling pendek membutuhkan O(n²) langkah.

Coba setiap panjang untuk bagian pertama

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Apa pun rencananya, potongan di ujung kiri memiliki panjang k dari 1 hingga panjang batang dan menghasilkan prices[k-1]; sisa rencana memotong batang dengan panjang length-k. Jadi, best(length) bernilai 0 untuk panjang 0, dan selain itu bernilai nilai terbesar dari prices[k-1] + best(length-k) untuk semua k, dengan k = length berarti menjual batang secara utuh. Setiap rencana memiliki potongan pertama, jadi nilai maksimum ini mencakup semua rencana.

Setiap pemanggilan bercabang ke semua panjang yang lebih pendek, jadi jumlah pemanggilan berlipat ganda untuk setiap satuan panjang: batang dengan panjang 40 menghasilkan sekitar 2^40, atau 10^12, pemanggilan.

Algoritma

Tulis best(length), yang mengembalikan 0 untuk panjang 0.
Untuk setiap potongan pertama k dari 1 hingga length, hitung prices[k-1] + best(length-k).
Kembalikan nilai terbesar dari nilai-nilai tersebut.
Kembalikan best(n).

def cutRod(prices):
    # The most money a rod of this length can earn
    def best(length):
        top = 0
        for piece in range(1, length + 1):
            # sell a first piece of this length, then cut the rest as well as possible
            top = max(top, prices[piece - 1] + best(length - piece))
        return top

    return best(len(prices))

Harga terbaik untuk setiap panjang, mulai dari yang terpendek

Intuisi

Rekursi menghitung ulang nilai yang sama: best(2) diminta oleh best(3), best(4), dan setiap batang yang lebih panjang. Hanya ada n+1 panjang, jadi hitung masing-masing sekali ke dalam sebuah array best. Suatu panjang hanya membaca panjang yang lebih pendek, jadi mengisi array dari 0 ke atas memastikan setiap nilai sudah siap saat dibaca.

Pada [2, 5, 7, 8]: best[1] bernilai 2, best[2] adalah yang lebih besar antara 2 + 2 dan 5, yaitu 5, best[3] bernilai 7, dan best[4] adalah yang terbesar antara 2 + 7, 5 + 5, 7 + 2, dan 8, yaitu 10.

Tidak seperti knapsack 0/1, best[len-k] mungkin sudah berisi potongan dengan panjang k, dan memang itu yang kamu inginkan, karena suatu panjang bisa dipotong sesering yang kamu mau. Panjang len mencoba potongan pertama dengan panjang 1 hingga len: totalnya n(n+1)/2 langkah, sekitar 5 × 10^5 untuk batang sepanjang 1000.

Algoritma

Buat best dengan n + 1 entri, semuanya 0.
Untuk setiap length dari 1 hingga n, coba setiap potongan pertama k dari 1 hingga length.
Hitung prices[k-1] + best[length-k] dan simpan nilai terbesar di best[length].
Kembalikan best[n].

def cutRod(prices):
    n = len(prices)
    # best[length]: the most money a rod of that length can earn
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            # a first piece of this length, then the best for what is left
            earned = prices[piece - 1] + best[length - piece]
            if earned > best[length]:
                best[length] = earned
    return best[n]

Jebakan dan kasus tepi

Membaca prices[k] untuk panjang k. Itu memberi harga untuk setiap potongan yang satu ukuran terlalu panjang dan melewati batas saat k = n. Gunakan prices[k-1].
Tidak menyertakan k = length, yaitu potongan yang tidak dipotong. Akibatnya, best[1] tetap 0, dan [1, 3, 8] menghasilkan nilai 3, bukan 8.
Memotong secara serakah berdasarkan harga per unit terbaik. Pada [2, 7, 11, 13], panjang 3 menghasilkan harga per unit tertinggi, tetapi 11 untuk potongan itu ditambah 2 untuk sisanya menghasilkan 13, sedangkan dua potongan dengan panjang 2 menghasilkan 14.
Menyimpan hasil rekursi top-down di Python. Rekursi tetap bertingkat sedalam panjang batang: batang sepanjang 1000 menghasilkan 1001 pemanggilan bertingkat, melebihi batas bawaan 1000. Isi array dari bawah ke atas.

Pertanyaan yang sering diajukan4

Apa kompleksitas waktu dari masalah pemotongan batang?

Tabel membutuhkan waktu O(n²) dan memori O(n): panjang len mencoba len potongan pertama, dengan total n(n+1)/2 percobaan. Tanpa jawaban yang disimpan, rekursi membuat tepat 2^n pemanggilan untuk batang dengan panjang n, karena setiap panjang memanggil semua panjang yang lebih pendek.

Mengapa pemotongan batang merupakan masalah knapsack tanpa batas?

Anggap setiap potongan dengan panjang k sebagai barang dengan bobot k dan nilai prices[k-1], dengan jumlah yang tidak terbatas, dan batang sebagai tas berkapasitas n yang harus diisi tepat sampai penuh. Jadi, nilai total terbaik dari barang-barang tersebut adalah harga terbaik untuk batang itu.

Bagaimana cara menentukan tempat untuk memotong batang?

Simpan, untuk setiap panjang, potongan pertama k yang menghasilkan harga terbaiknya. Mulai dari panjang n: potong satu bagian dengan panjang yang tersimpan, pindah ke panjang yang tersisa, lalu ulangi hingga mencapai 0. Potongan-potongan tersebut membentuk satu rencana terbaik.

Bagaimana solusi berubah jika setiap potongan membutuhkan biaya?

Menjual batang secara utuh tidak memerlukan pemotongan, sedangkan setiap potongan pertama lainnya menambah satu pemotongan. Jadi, best[len] menjadi nilai yang lebih besar antara prices[len-1] dan nilai terbesar prices[k-1] + best[len-k] - cost untuk k yang lebih kecil dari len. Bagian tabel lainnya tetap sama.

def cutRod(prices):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

prices = [2, 5, 7, 8]

Output yang diharapkan