0/1 Knapsack Problem
Kamu memiliki n barang. Barang i memiliki berat weights[i] dan nilai values[i]. Tasmu dapat membawa total berat paling banyak capacity. Setiap barang hanya tersedia satu buah, dan kamu bisa memasukkannya secara utuh ke dalam tas atau meninggalkannya. Kembalikan total nilai terbesar yang bisa kamu masukkan ke dalam tas.
Fungsi
- weightsinteger-array
- berat setiap item
- valuesinteger-array
- nilai setiap item
- capacityinteger
- berat maksimum yang dapat dibawa tas
- Mengembalikaninteger
- nilai total terbesar dari barang-barang yang beratnya muat dalam kapasitas
Batasan
1 ≤ n ≤ 100, dengann = weights.length = values.length1 ≤ weights[i] ≤ 10001 ≤ values[i] ≤ 1041 ≤ capacity ≤ 1000
Contoh
- Input
- weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
- Output
- 17
- Penjelasan
- Barang 0 dan 2 memiliki berat 4 + 3 = 7 dan bernilai 10 + 7 = 17. Jika barang paling berharga dikemas terlebih dahulu (berat 5, nilai 12), hanya tersisa ruang untuk barang 1, sehingga nilainya 16.
- Input
- weights = [5, 4, 3]values = [10, 7, 6]capacity = 7
- Output
- 13
- Penjelasan
- Barang 1 dan 2 memiliki berat 4 + 3 = 7 dan bernilai 7 + 6 = 13. Barang 0 menghasilkan 2 per unit berat, sama banyaknya dengan barang lain, tetapi setelah memasukkannya, sisa 2 unit tidak cukup untuk memuat barang apa pun.
- Input
- weights = [6, 8]values = [5, 9]capacity = 5
- Output
- 0
- Penjelasan
- Kedua barang memiliki berat lebih dari 5, jadi tidak ada yang muat dan nilai tas kosong adalah 0.
Pertanyaan lanjutan
Misalkan kapasitasnya bisa mencapai 10^9, sementara jumlah nilainya paling banyak 10^4. Apa yang akan kamu gunakan sebagai indeks tabel?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Tentukan item secara berurutan, mulai dari item 0. Baik kamu memasukkannya maupun meninggalkannya, kamu menghadapi pertanyaan yang sama tentang item-item setelahnya. Angka mana dalam pertanyaan itu yang berubah?
Nilai terbaik mulai dari sini hanya bergantung pada dua angka: item mana yang sedang kamu lihat dan berapa banyak ruang yang tersisa. Dengan 100 item dan kapasitas 1000, ada sekitar 10^5 pasangan seperti itu, jadi kamu bisa menghitung masing-masing sekali lalu menyimpannya.
Simpan
best[c]untuk setiap kapasitascdari 0 hinggacapacity, semuanya bernilai 0 pada awalnya. Untuk item dengan beratwdan nilaiv, telusuricdaricapacityturun hinggaw, lalu simpan nilai yang lebih besar antarabest[c]danbest[c-w] + v. Menelusuri dari nilai besar ke kecil mencegah item dimasukkan dua kali.
Solusi
Tidak ada urutan greedy yang berhasil: mengemas barang paling bernilai terlebih dahulu menghasilkan 16, bukan 17, pada contoh pertama. Nilai terbaik dari barang i dan seterusnya hanya bergantung pada i dan ruang yang tersisa, yang berupa bilangan bulat hingga 1000. Satu sel tabel untuk setiap pasangan menghasilkan O(n × capacity), dan satu baris saja cukup jika kamu menelusuri kapasitas dari yang terbesar ke terkecil.
Coba kedua pilihan untuk setiap item
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Misalkan best(i, room) adalah jumlah nilai terbesar yang bisa ditambahkan item mulai dari i dan seterusnya dengan room unit ruang kosong; setelah item terakhir, nilainya 0. Melewati item i menghasilkan best(i+1, room). Memasukkannya, jika weights[i] ≤ room, menghasilkan values[i] + best(i+1, room-weights[i]). Ambil nilai yang lebih besar. Setiap cara mengemas barang yang muat merupakan satu rangkaian pilihan untuk mengemas dan melewati barang, dan rekursi mencoba semuanya.
Setiap item menggandakan jumlah jalur. Jika semua 100 item muat bersama, seperti saat masing-masing memiliki berat 10 di dalam tas berkapasitas 1000, jumlahnya adalah 2^100 jalur.
Algoritma
- Tulis
best(i, room); kembalikan 0 ketikaimelewati item terakhir. - Tetapkan
skipkebest(i+1, room). - Jika
weights[i] > room, kembalikanskip. - Jika tidak, kembalikan nilai yang lebih besar antara
skipdanvalues[i] + best(i+1, room-weights[i]). - Kembalikan
best(0, capacity).
def knapsack(weights, values, capacity):
n = len(weights)
# The most value items i, i+1, ... can add with room units of weight left
def best(i, room):
if i == n:
return 0
skip = best(i + 1, room)
if weights[i] > room:
return skip
take = values[i] + best(i + 1, room - weights[i])
return max(skip, take)
return best(0, capacity)Isi tabel berdasarkan item dan kapasitas
Intuisi
Rekursi mencapai pasangan (i, room) yang sama melalui banyak jalur. Jumlah pasangan paling banyak 101 × 1001, sekitar 10^5, jadi hitung masing-masing sekali.
Misalkan best[i][c] adalah nilai terbesar yang dapat dimasukkan oleh i item pertama ke dalam tas berkapasitas c; baris 0 semuanya 0. Untuk item i-1 dengan berat w dan nilai v, tidak memasukkannya memberi best[i-1][c], sedangkan memasukkannya, jika w ≤ c, memberi best[i-1][c-w] + v. Baris i hanya membaca baris i-1, jadi setiap item masuk ke sebuah sel paling banyak sekali.
Pada contoh pertama, item 2 (berat 3, nilai 7) menaikkan kapasitas 7 menjadi best[2][4] + 7 = 17. Item 3 kemudian hanya menghasilkan best[3][2] + 12 = 16, jadi jawabannya tetap 17.
Algoritma
- Buat tabel dengan n+1 baris dan capacity+1 kolom, semuanya bernilai 0.
- Untuk setiap baris
idari 1 hingga n, ambilw = weights[i-1]danv = values[i-1]. - Untuk setiap kapasitas
c, tetapkanbest[i][c]menjadibest[i-1][c]. - Jika
w ≤ cdanbest[i-1][c-w] + vlebih besar, simpan nilai itu. - Kembalikan
best[n][capacity].
def knapsack(weights, values, capacity):
n = len(weights)
# best[i][c]: the most value from the first i items within capacity c
best = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
best[i][c] = best[i - 1][c] # leave item i-1 out
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v # put it in
return best[n][capacity]Satu baris, kapasitas ditelusuri dari atas ke bawah
Intuisi
Baris i hanya membutuhkan baris i-1, jadi simpan satu baris best[c] dan timpa nilainya item demi item. Arah penelusuran menentukan apakah jawabannya benar.
Jika menelusuri c ke atas, best[c-w] mungkin sudah mencakup item saat ini. Satu item dengan bobot 3 dan nilai 5, dengan kapasitas 6, membuat kapasitas 3 bernilai 5, lalu kapasitas 6 membacanya dan menjadi 10: dua salinan. Jika menelusuri dari capacity ke w ke bawah, sel yang kamu baca berada di bawah sel yang kamu tulis dan akan ditimpa kemudian, sehingga nilainya masih sama dengan nilai dari baris sebelumnya.
Penelusuran ke atas adalah perulangan yang tepat saat item tersedia dalam jumlah tak terbatas. Di sini, waktu tetap O(n × capacity) dan memori berkurang menjadi satu baris.
Algoritma
- Buat
bestdengancapacity + 1entri, semuanya 0. - Untuk setiap item dengan bobot
wdan nilaiv, telusuricdaricapacityturun hinggaw. - Jika
best[c-w] + vlebih besar daripadabest[c], simpan nilai tersebut dibest[c]. - Kembalikan
best[capacity].
def knapsack(weights, values, capacity):
# best[c]: the most value from the items seen so far within capacity c
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Walk the capacities downward so each item goes in at most once
for c in range(capacity, w - 1, -1):
if best[c - w] + v > best[c]:
best[c] = best[c - w] + v
return best[capacity]
Jebakan dan kasus tepi
- Menelusuri kapasitas dari kecil ke besar dalam versi satu baris membuat satu barang dimasukkan dua kali: satu barang dengan berat 3 dan nilai 5 di dalam tas berkapasitas 6 menghasilkan skor 10, bukan 5.
- Menggunakan satu baris dengan
capacityentri, bukancapacity + 1. Mengembalikanbest[capacity-1]kemudian mengabaikan pengemasan yang memenuhi kapasitas tas dengan tepat, seperti barang dengan berat 1 di dalam tas berkapasitas 1. - Memulai entri dengan negatif tak terhingga. Tas tidak harus penuh, jadi setiap entri dimulai dari 0. Dengan negatif tak terhingga, contoh ketiga mengembalikan negatif tak terhingga, bukan 0.
- Barang yang lebih berat daripada kapasitas tas harus dilewati. Dalam contoh ketiga, rentang tertutup
w...capacitymenghentikan program di Swift, sedangkan(w+1):(capacity+1)menghitung mundur di R.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu dari masalah knapsack 0/1?
Tabel ini berjalan dalam waktu O(n × capacity), sekitar 10^5 langkah untuk 100 item dan capacity 1000, dan versi satu baris menggunakan memori O(capacity). Batas ini bersifat pseudo-polinomial: nilainya bertambah seiring nilai capacity, bukan jumlah digitnya. Masalah umumnya bersifat NP-hard.
Mengapa algoritma greedy tidak berhasil untuk masalah knapsack 0/1?
Aturan greedy tidak pernah membatalkan pilihan, bahkan saat barang itu menyisakan ruang yang tidak bisa diisi oleh barang lain. Dengan kapasitas 7, barang dengan berat 5 dan nilai 10 memiliki rasio terbaik yang sama, tetapi gabungan barang dengan berat 4 dan 3 bernilai 13. Greedy berdasarkan rasio hanya optimal untuk knapsack fraksional, tempat kamu bisa membagi barang.
Bagaimana cara mengetahui item mana yang dipilih oleh knapsack 0/1?
Pertahankan seluruh tabel, lalu telusuri kembali dari best[n][capacity]. Jika best[i][c] berbeda dari best[i-1][c], item i-1 dimasukkan, jadi catat item itu dan kurangi bobotnya dari c. Jika tidak, pindah ke baris i-1 dengan c yang sama.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def knapsack(weights, values, capacity):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
weights = [4, 2, 3, 5] values = [10, 4, 7, 12] capacity = 7
Output yang diharapkan
17