Uji Pemahaman Knapsack

Apa yang dimaksud dengan knapsack?

• Knapsack adalah masalah optimasi yang berkaitan dengan pemilihan item untuk memaksimalkan nilai dalam batasan kapasitas.

• Knapsack adalah jenis tas untuk membawa barang.

• Knapsack adalah metode untuk menyimpan data dalam database.

• Knapsack adalah algoritma untuk menghitung waktu.

Sebutkan metode pemecahan knapsack yang umum digunakan!

• Metode greedy yang tidak efisien

• Algoritma pencarian biner

• Algoritma brute force

• Pemrograman dinamis, greedy algorithm, backtracking

Jelaskan algoritma greedy dalam konteks knapsack!

• Algoritma greedy memilih item dengan berat tertinggi untuk mengisi knapsack.

• Algoritma greedy memilih item dengan rasio nilai/berat tertinggi untuk mengisi knapsack.

• Algoritma greedy mengisi knapsack dengan item secara acak tanpa mempertimbangkan nilai.

• Algoritma greedy memilih item dengan nilai tertinggi tanpa memperhatikan berat.

Bagaimana cara mengimplementasikan knapsack dalam Python?

• def knapsack(weights, values): return sum(values)

• def knapsack(capacity, weights): return weights[0] if weights else 0

• def knapsack(capacity, weights, values, n): K = [[0 for x in range(capacity + 1)] for x in range(n + 1)] for i in range(n + 1): for w in range(capacity + 1): if i == 0 or w == 0: K[i][w] = 0 elif weights[i-1] <= w: K[i][w] = max(values[i-1] + K[i-1][w - weights[i-1]], K[i-1][w]) else: K[i][w] = K[i-1][w] return K[n][capacity]

• def knapsack(capacity): return capacity * 2

Sebutkan beberapa aplikasi knapsack dalam kehidupan sehari-hari!

• Desain grafis untuk iklan

• Pengelolaan waktu kerja

• Pengelolaan anggaran, pemilihan barang untuk perjalanan, pengalokasian sumber daya dalam proyek.

• Pembuatan makanan

Apa perbedaan antara algoritma knapsack 0/1 dan knapsack fractional?

• Knapsack 0/1 membolehkan item diambil utuh, sedangkan knapsack fractional membolehkan pengambilan sebagian item.

• Knapsack 0/1 hanya dapat digunakan untuk item dengan nilai yang sama, sedangkan knapsack fractional tidak.

• Knapsack 0/1 membolehkan pengambilan sebagian item, sedangkan knapsack fractional membolehkan item diambil utuh.

• Knapsack 0/1 dan knapsack fractional memiliki cara pengambilan item yang sama.

Mengapa algoritma greedy tidak selalu memberikan solusi optimal untuk knapsack?

• Algoritma greedy tidak selalu memberikan solusi optimal untuk knapsack karena ia hanya mempertimbangkan pilihan lokal terbaik tanpa melihat kombinasi global.

• Algoritma greedy selalu memberikan solusi optimal untuk knapsack.

• Algoritma greedy hanya digunakan untuk masalah yang tidak melibatkan knapsack.

• Algoritma greedy mempertimbangkan semua kombinasi secara bersamaan.

Berikan contoh kasus nyata di mana knapsack dapat diterapkan!

• Menghitung jumlah barang dalam keranjang belanja online.

• Menentukan rute tercepat untuk pengiriman barang.

• Membandingkan harga produk di berbagai toko.

• Pemilihan produk untuk pameran dagang dengan batasan ruang dan nilai.

Apa saja langkah-langkah dalam menyelesaikan masalah knapsack?

• Membuat diagram alir untuk setiap item

• Menggunakan algoritma greedy untuk memilih item

• Langkah-langkah dalam menyelesaikan masalah knapsack adalah menentukan kapasitas, nilai dan berat item, menggunakan pendekatan dinamis, membuat tabel, mengisi tabel, dan mengambil keputusan akhir.

• Menghitung total berat semua item

Bagaimana cara menganalisis kompleksitas waktu dari algoritma knapsack?

• O(nW) untuk algoritma dinamis dan O(2^n) untuk brute force.

• O(n + W) untuk algoritma dinamis

• O(n log n) untuk brute force

• O(n^2) untuk algoritma dinamis