Masalah knapsack
Pelajaran 7 dari 15 dalam kursus Dasar-Dasar Pemrograman Dinamis di Coddy.
Masalah Knapsack adalah masalah optimasi klasik dalam ilmu komputer. Pernyataan masalahnya sederhana: diberikan sekumpulan barang, masing-masing dengan berat dan nilai, tentukan barang yang akan dimasukkan ke dalam kumpulan agar berat totalnya kurang dari atau sama dengan batas yang ditentukan dan nilai totalnya maksimal.
Ada dua jenis masalah knapsack:
- Knapsack 0/1: Dalam versi ini, pencuri tidak dapat mengambil sebagian dari barang, mereka harus mengambilnya secara utuh atau meninggalkannya.
- Knapsack fraksional: Dalam versi ini, pencuri dapat mengambil sebagian dari barang, yaitu sebagian dari suatu barang dapat diambil.
Tantangan
SedangTulis fungsi bernama knapsack yang menyelesaikan masalah knapsack 0/1. Fungsi ini harus menerima tiga input:
- List bobot dari n item (w1, w2, ... , wn).
- List nilai dari n item (v1, v2, ... , vn).
- Kapasitas bobot maksimum knapsack (W).
Fungsi ini kemudian harus menghasilkan nilai maksimum yang bisa dicapai dengan mengisi knapsack.
Contoh:
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
knapsack(weights, values, W)Output:
220 # taking the 2 largest itemsCoba sendiri
def knapsack(wrights, values, W):
# Tulis kodemu di siniSemua pelajaran di Dasar-Dasar Pemrograman Dinamis
3Algoritma pemrograman dinamis
Subsekuens bersama terpanjangMasalah knapsackMasalah penukaran koinJarak editLatihan sendiri: Compiler Python online