Fractional Knapsack

Q: Berapa kompleksitas waktu dari masalah fractional knapsack?

Mengurutkan item berdasarkan nilai per berat membutuhkan O(n log n) , dan pengisian dilakukan dalam satu kali lintasan, sehingga totalnya O(n log n) dengan ruang O(n) untuk urutannya. Memindai item dengan kepadatan tertinggi di setiap putaran membutuhkan O(n²) .

Q: Bagaimana cara menyelesaikan masalah fractional knapsack tanpa bilangan floating point?

Dengan bobot positif, a / b > c / d adalah pengujian yang sama dengan a × d > c × b , jadi bandingkan kepadatan dengan mengalikan silang. Nilai terbaik berupa bilangan bulat ditambah satu pecahan, values[i] × room / weights[i] untuk item yang dipotong, jadi satu pembagian bilangan bulat menghasilkan jawaban yang dibulatkan ke bawah dengan tepat.

SedangGreedy Pengurutan

+10

Kamu memiliki n barang. Barang i bernilai values[i] dan memiliki berat weights[i]. Tasmu dapat menampung berat total paling banyak capacity, dan kamu boleh mengambil sebagian dari suatu barang: sebagian barang i dengan berat w bernilai values[i] × w / weights[i].

Tulis fungsi bernama fractionalKnapsack yang mengembalikan nilai total terbesar yang dapat dibawa tas, dibulatkan ke bawah menjadi bilangan bulat.

Fungsi

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: nilai setiap item
weightsinteger-array: berat setiap item
capacityinteger: berat maksimum yang dapat ditampung tas
Mengembalikaninteger: nilai total terbesar yang muat di dalam tas, dibulatkan ke bawah

Batasan

1 ≤ n ≤ 5000, dengan n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

Contoh

Input: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Output: 151
Penjelasan: Nilai tiap satuan berat barang-barang tersebut adalah 5, 3, 6, dan 2.5. Barang 2 dan 0 dimasukkan secara utuh dengan nilai 70, sehingga tersisa kapasitas 27, lalu 27 dari 30 satuan barang 1 menambah nilai 81, sehingga totalnya 151.

Input: values = [10, 7]weights = [4, 3]capacity = 5
Output: 12
Penjelasan: Item 0 bernilai 2.5 per unit dan item 1 sekitar 2.33, jadi item 0 dimasukkan seluruhnya sebanyak 10. Satu dari 3 unit item 1 menambahkan 7 / 3, dan 12 sepertiga dibulatkan ke bawah menjadi 12.

Pertanyaan lanjutan

Bisakah kamu menemukan jawabannya dalam waktu O(n), tanpa mengurutkan semua item?

Petunjuk

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

0 dari 3 dibuka

Solusi

Karena kamu dapat memotong barang, masalah ini menggunakan pendekatan greedy, tidak seperti knapsack 0/1: setiap unit berat harus berasal dari barang yang tersisa dengan nilai per unit tertinggi. Urutkan berdasarkan kepadatan tersebut, lalu isi tas sesuai urutan. Bandingkan kepadatannya dengan perkalian silang dan bulatkan ke bawah hanya barang yang kamu potong, sehingga tidak ada pecahan yang disimpan.

Pilih item paling padat di setiap putaran

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Isi tas mulai dari barang dengan kepadatan tertinggi: ambil seluruh barang jika muat, jika tidak, ambil bagian yang memenuhi tas lalu berhenti. Cari barang belum terpakai dengan kepadatan tertinggi dengan memindai semuanya, bandingkan values[i] × weights[j] dengan values[j] × weights[i] alih-alih membagi. Dengan bobot positif, hasilnya sama, dan kedua hasil perkalian tetap paling tinggi 10^8.

Memilih barang dengan kepadatan tertinggi terlebih dahulu adalah yang terbaik: jika muatan berisi sejumlah bobot dari barang dengan kepadatan lebih rendah sementara barang yang lebih padat belum sepenuhnya dimasukkan, menukar bobot itu dengan barang yang lebih padat tidak akan mengurangi nilai. Terus lakukan pertukaran hingga kamu mendapatkan muatan dengan barang berurutan dari kepadatan tertinggi.

Hingga n putaran, setiap putaran memindai barang yang belum terpakai, sekitar n²/2 = 12.5 juta perbandingan untuk n = 5000.

Algoritma

Tandai setiap item sebagai belum digunakan, lalu atur room = capacity dan total = 0.
Selama masih ada ruang, periksa item yang belum digunakan untuk menemukan item dengan kepadatan tertinggi, lalu bandingkan kepadatannya menggunakan perkalian silang.
Jika tidak ada item tersisa, berhenti. Jika masih ada, tandai item tersebut sebagai telah digunakan.
Jika item tersebut muat, tambahkan nilainya ke total dan kurangi room dengan beratnya. Jika tidak muat, tambahkan values[i] × room / weights[i] menggunakan pembagian bilangan bulat, lalu berhenti.
Kembalikan total.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

Urutkan berdasarkan nilai per berat

Intuisi

Pemindaian menemukan item dengan densitas tertinggi berulang kali, tetapi urutannya tidak pernah berubah dari satu putaran ke putaran berikutnya. Urutkan item sekali saja, dari yang paling padat, menggunakan perbandingan silang yang sama. Item dengan densitas sama bisa diurutkan dalam urutan apa pun, karena nilainya sama per unit.

Ambil item secara utuh selama masih muat. Item pertama yang tidak muat adalah satu-satunya item yang kamu potong: item itu menambahkan values[i] × room / weights[i], dan pembagian bilangan bulat membulatkannya ke bawah. Semua item sebelumnya diambil secara utuh, jadi pembulatan pada satu suku ini menghasilkan jawaban yang tepat. Pengurutan memerlukan O(n log n) dan penelusuran memerlukan O(n).

Algoritma

Buat daftar indeks item, lalu urutkan dari yang paling padat menggunakan perbandingan dengan perkalian silang.
Tetapkan room = capacity dan total = 0.
Untuk setiap item dalam urutan tersebut, jika weights[i] ≤ room, tambahkan nilainya dan kurangi room sebesar bobotnya.
Jika tidak, tambahkan values[i] × room / weights[i] dengan pembagian bilangan bulat, lalu berhenti.
Kembalikan total.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

Jebakan dan kasus tepi

Mengurutkan hanya berdasarkan nilai atau berat. Dalam contoh pertama, barang bernilai 90 hanya berada di urutan ketiga berdasarkan kepadatan. Jika mengambilnya terlebih dahulu, hanya tersisa ruang untuk setengah dari barang bernilai 50, sehingga totalnya 115, bukan 151.
Membagi sebelum mengalikan. Dengan nilai 13, berat 7, dan ruang 3, 13 / 7 * 3 dalam operasi bilangan bulat menghasilkan 3, sedangkan 13 * 3 / 7 menghasilkan 5 yang benar.
Mengira suatu barang selalu harus dipotong. Dalam contoh ketiga, semua barang muat, dan jawabannya adalah jumlah semua nilai, yaitu 13.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari masalah fractional knapsack?

Mengurutkan item berdasarkan nilai per berat membutuhkan O(n log n), dan pengisian dilakukan dalam satu kali lintasan, sehingga totalnya O(n log n) dengan ruang O(n) untuk urutannya. Memindai item dengan kepadatan tertinggi di setiap putaran membutuhkan O(n²).

Mengapa pendekatan greedy berhasil untuk fractional knapsack, tetapi tidak untuk 0/1 knapsack?

Pemotongan memungkinkan kamu menukar berat barang yang kurang padat dengan barang yang lebih padat. Tanpa pemotongan, barang yang padat bisa menyisakan ruang yang tidak dapat diisi barang lain. Dengan nilai 8, 11, 15, berat 2, 3, 4, dan kapasitas 7, memilih yang paling padat terlebih dahulu mengambil berat 2 dan 4 dengan nilai 23, sedangkan berat 3 dan 4 menghasilkan nilai 26. Versi 0/1 membutuhkan pemrograman dinamis.

Bagaimana cara menyelesaikan masalah fractional knapsack tanpa bilangan floating point?

Dengan bobot positif, a / b > c / d adalah pengujian yang sama dengan a × d > c × b, jadi bandingkan kepadatan dengan mengalikan silang. Nilai terbaik berupa bilangan bulat ditambah satu pecahan, values[i] × room / weights[i] untuk item yang dipotong, jadi satu pembagian bilangan bulat menghasilkan jawaban yang dibulatkan ke bawah dengan tepat.

def fractionalKnapsack(values, weights, capacity):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

Output yang diharapkan