Saya mencari untuk memaksimalkan jumlah bintang yang diberikan anggaran tertentu dan batas maksimum pada kombinasi.
Contoh pertanyaan:
Dengan anggaran 500 euro, hanya mengunjungi restoran maksimum yang diizinkan atau kurang, makan dan mengumpulkan bintang sebanyak mungkin.
Saya ingin menulis algoritma yang efisien, yang berpotensi memproses 1 juta contoh restoran hingga 10 restoran maks.
Catatan, ini adalah pos silang dari pertanyaan yang saya ajukan kemarin: Java: Dapatkan kombinasi paling efisien dari daftar besar objek berdasarkan bidang
Solusi di bawah ini akan menetapkan $ 15 per bintang ke r8
Restoran, yang berarti bahwa ketika membuat daftar, itu menempatkan itu ke dalam daftar pertama, dan dengan $ 70 yang tersisa itu hanya bisa mendapatkan 2 bintang lagi memberikan total 4 bintang. Namun, jika itu cukup pintar untuk melewati r8
restoran (meskipun itu adalah rasio dolar per bintang terbaik) r1
restoran sebenarnya akan menjadi pilihan yang lebih baik untuk anggaran, karena biaya $ 100 dan 5 bintang.
Adakah yang bisa membantu mencoba masalah dan mengalahkan solusi saat ini?
import itertools
class Restaurant():
def __init__(self, cost, stars):
self.cost = cost
self.stars = stars
self.ratio = cost / stars
def display(self):
print("Cost: $" + str(self.cost))
print("Stars: " + str(self.stars))
print()
r1 = Restaurant(100, 5)
r2 = Restaurant(140, 3)
r3 = Restaurant(90, 4)
r4 = Restaurant(140, 3)
r5 = Restaurant(120, 4)
r6 = Restaurant(60, 1)
r7 = Restaurant(40, 1)
r8 = Restaurant(30, 2)
r9 = Restaurant(70, 2)
r10 = Restaurant(250, 5)
print()
print("***************")
print("** Unsorted: **")
print("***************")
print()
restaurants = [r1, r2, r3, r4, r5, r6, r7, r8, r9, r10]
for restaurant in restaurants:
print(restaurant.ratio, restaurant.stars)
print()
print("***************")
print("** Sorted: **")
print("***************")
print()
sorted_restaurants = sorted(restaurants, key = lambda x: x.ratio, reverse = True)
for restaurant in sorted_restaurants:
print(restaurant.ratio, restaurant.stars)
print()
print("*********************")
print("** Begin Rucksack: **")
print("*********************")
print()
max = 5
budget = 100
spent = 0
quantity = 0
rucksack = []
for i in itertools.count():
if len(rucksack) >= max or i == len(sorted_restaurants):
break
sorted_restaurants[i].display()
if sorted_restaurants[i].cost + spent <= budget:
spent = spent + sorted_restaurants[i].cost
rucksack.append(sorted_restaurants[i])
print("Total Cost: $" + str(sum([x.cost for x in rucksack])))
print("Total Stars: " + str(sum([x.stars for x in rucksack])))
print()
print("*****************")
print("** Final List: **")
print("*****************")
print()
for restaurant in rucksack:
restaurant.display()
budget
= berat ransel maksimal dalam kg,max
= jumlah barang yang dapat disimpan ransel,stars
= beberapa nilai pada barang tersebut dancost
= berat barang dalam kgr8
Restoran, yang berarti bahwa ketika membuat daftar, ia menempatkan itu ke dalam daftar pertama, dan dengan sisa $ 70 itu hanya bisa mendapatkan 2 bintang lagi. Namun, jika itu cukup pintar untuk melompati itu (meskipun itu adalah rasio dolar per bintang terbaik,r1
restoran sebenarnya akan menjadi pilihan yang lebih baik untuk anggaran, karena itu adalah $ 100 biaya dan 5 bintangJawaban:
Kedengarannya seperti masalah Anda hampir sama dengan masalah Knapsack: Maksimalkan nilai mengingat batasan berat dan volume tertentu. Nilai dasarnya = total bintang, berat = harga, batas ransel = total anggaran. Sekarang ada kendala tambahan total "item" (kunjungan restoran) tetapi itu tidak mengubah intinya.
Seperti Anda mungkin atau mungkin tidak tahu, masalah ransel adalah NP keras, yang berarti tidak ada algoritma dengan penskalaan waktu polinomial diketahui.
Namun, mungkin ada algoritma pseudopolinomial yang efisien menggunakan pemrograman dinamis, dan tentu saja ada heuristik yang efisien, seperti heuristik "serakah" yang tampaknya telah Anda temukan. Heuristik ini melibatkan mulai mengisi dengan item "kepadatan" tertinggi (sebagian besar bintang per dolar) terlebih dahulu. Seperti yang telah Anda lihat, heuristik ini gagal menemukan optimal yang sebenarnya dalam beberapa kasus.
Pendekatan pemrograman dinamis harus cukup bagus di sini. Ini didasarkan pada rekursi: Dengan anggaran B dan sejumlah kunjungan yang tersisa V, restoran apa yang paling baik untuk dikunjungi dari sekumpulan restoran R?
Lihat di sini: https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem
Pada dasarnya kami mendefinisikan larik
m
untuk "bintang maksimum", di manam[i, b, v]
jumlah bintang maksimum yang bisa kami dapatkan ketika kami diizinkan mengunjungi restoran hingga (dan termasuk) jumlah restorani
, paling banyak belanjab
, dan mengunjungi di sebagian besarv
restoran (batas) .Sekarang, kami dari bawah ke atas mengisi array ini. Misalnya,
m[0, b, v] = 0
untuk semua nilaib
danv
karena jika kita tidak dapat pergi ke restoran mana pun, kita tidak dapat memperoleh bintang.Juga,
m[i, b, 0] = 0
untuk semua nilaii
danb
karena jika kami menggunakan semua kunjungan kami, kami tidak dapat memperoleh bintang lagi.Baris berikutnya juga tidak terlalu sulit:
m[i, b, v] = m[i - 1, b, v] if p[i] > b
dimanap[i]
harga makan di restorani
. Apa kata garis ini? Nah, jika restorani
lebih mahal daripada uang yang tersisa (b
) maka kita tidak bisa pergi ke sana. Yang berarti jumlah maksimum bintang yang dapat kita peroleh adalah sama apakah kita termasuk restoran hinggai
atau hanya sampaii - 1
.Baris berikutnya agak rumit:
m[i, b, v] = max(m[i-1, b, v]), m[i-1, b - p[i], v-1] + s[i]) if p[i] <= b
Fiuh.
s[i]
adalah jumlah bintang yang kamu dapatkan dari restorani
btw.Apa kata garis ini? Ini adalah jantung dari pendekatan pemrograman dinamis. Ketika mempertimbangkan jumlah maksimum bintang yang bisa kita dapatkan ketika melihat restoran hingga dan termasuk
i
, maka dalam solusi yang dihasilkan kita pergi ke sana atau tidak, dan kita "hanya" harus melihat yang mana dari dua jalur ini yang mengarah ke lebih banyak bintang:Jika kita tidak pergi ke restoran
i
, maka kita menyimpan jumlah uang yang sama dan sisa kunjungan. Jumlah maksimal bintang yang bisa kita dapatkan di jalur ini sama dengan jika kita bahkan tidak melihat restorani
. Itu bagian pertama dalammax
.Tetapi jika kita pergi ke restoran
i
, maka kita hanya memilikip[i]
sedikit uang, satu kunjungan lebih sedikit, dans[i]
lebih banyak bintang. Itu bagian kedua dalammax
.Sekarang pertanyaannya sederhana: mana dari keduanya yang lebih besar.
Anda dapat membuat array ini dan mengisinya dengan loop yang relatif sederhana (ambil inspirasi dari wiki). Ini hanya memberi Anda jumlah bintang, bukan daftar restoran yang sebenarnya untuk dikunjungi. Untuk itu, tambahkan beberapa pembukuan tambahan ke dalam perhitungan
w
.Saya harap informasi itu cukup untuk mengarahkan Anda ke arah yang benar.
Atau, Anda dapat menulis masalah Anda dalam hal variabel biner dan fungsi tujuan kuadratik dan menyelesaikannya pada annelaer kuantum D-Wave :-p Pesan saya jika Anda ingin tahu lebih banyak tentang itu.
sumber
Menggunakan ide yang sama dengan jawaban saya di sini :
Anda dapat membuat daftar mulai dari restoran "termurah" yang potensial .
Langkah-langkah algoritma:
Tentu saja, Anda tidak dapat memilih kembali restoran.
Saya pikir kasus terburuk, Anda harus menghitung 5x5x5 ... = 5 ^ 10 + 5 ^ 9 + ... + 5 ^ 2 + 5 (= sekitar 12 juta) solusi.
Dalam javascript
sumber