Ini adalah percobaan pertama saya dengan tantangan kompleksitas asimptotik meskipun saya senang dengan jawaban sepenuhnya dalam kode selama mereka datang dengan penjelasan tentang kompleksitas waktu mereka.
Saya memiliki masalah berikut.
Pertimbangkan tugas T_1, ... T_n dan procs M_1, ..., M_m. Setiap tugas membutuhkan sejumlah waktu untuk melakukan tergantung pada procs.
Setiap tugas juga membutuhkan biaya untuk melakukan tergantung pada procs.
Tugas-tugas harus dilakukan dalam urutan yang ketat (mereka tidak dapat dilakukan secara paralel) dan perlu waktu untuk mengubah proc. Tugas tidak dapat dipindahkan dari satu proc ke proc lain setelah dimulai.
Akhirnya, setiap tugas harus diselesaikan pada waktu tertentu.
tugas
Tujuannya adalah untuk memberikan algoritma (atau beberapa kode) yang diberikan lima tabel dari formulir di atas, meminimalkan total biaya untuk menyelesaikan semua tugas sambil memastikan semua tugas selesai dengan tenggat waktu mereka. Jika ini tidak mungkin, kami hanya melaporkan bahwa itu tidak dapat dilakukan.
skor
Anda harus memberikan kompleksitas Oh yang besar dari solusi Anda dalam hal variabel n, m dan d, di mana d adalah batas waktu terakhir. Seharusnya tidak ada konstanta yang tidak perlu dalam kompleksitas Oh Anda yang besar. Jadi O (n / 1000) harus ditulis sebagai O (n), misalnya.
Skor Anda dihitung hanya dengan menetapkan n = 100, m = 100 dan d = 1000 ke dalam kompleksitas yang Anda nyatakan. Anda ingin skor sekecil mungkin.
pemutus dasi
Dalam kasus seri, jawaban pertama menang.
catatan ditambahkan
log
dalam kompleksitas waktu jawaban akan diambil basis 2.
papan skor
- 10 ^ 202 dari KSFT ( Python ) Pertama kali diserahkan sehingga mendapat hadiah.
- 10 ^ 202 dari Dominik Müller ( Scala )
O(m ^ n)
. Tidak ada algoritma yang "lebih cepat" dari itu. Pemangkasan berdasarkan waktu atau biaya maksimum yang diperlukan tidak mengubah kompleksitas algoritme, juga tidak memiliki biaya dolar dan biaya waktu, karenanyad
bukan merupakan elemen kompleksitas.Jawaban:
Nilai: 10 ^ 202
Saya agak berharap kami memiliki dukungan LaTeX sekarang ...
Karena tidak ada orang lain yang menjawab, saya pikir saya akan mencoba, meskipun tidak terlalu efisien. Saya tidak yakin apa O besar itu, meskipun.
Saya pikir itu berhasil. Setidaknya, itu berlaku untuk satu-satunya test case yang diposting.
Dibutuhkan input seperti dalam pertanyaan, kecuali tanpa label nomor mesin atau tugas, dan dengan titik koma alih-alih jeda baris.
sumber
Periksa Semua - Scala
Perkiraan skor: 2m ^ n
Saya mulai dari setiap mesin dan beralih ke semua tugas untuk membuat semua permutasi melalui tugas dengan mesin yang berbeda yang memenuhi tenggat waktu. Berarti jika semuanya dalam waktu saya akan mendapatkan 9 kemungkinan jalur dengan 2 mesin dan 3 tugas. (m ^ n) Setelah itu, saya mengambil jalur dengan biaya terendah.
Input disusun seperti ini (-> menjelaskan bagian-bagiannya dan karenanya tidak boleh dimasukkan):
Dan ini kodenya:
Saya juga punya ide untuk memulai dari belakang. Karena Anda selalu dapat memilih mesin dengan biaya terendah jika waktunya lebih kecil maka selisih dari tenggat waktu sebelumnya ke yang baru. Tapi itu tidak akan mengurangi runtime maksimal jika tugas dengan biaya yang lebih baik membutuhkan waktu lebih lama dari batas waktu terakhir.
Memperbarui
======
Berikut ini adalah pengaturan lainnya. waktu:
biaya:
beralih waktu:
biaya beralih:
tenggat waktu:
Sebagai masukan ke dalam program saya:
Yang ini memiliki dua solusi: waktu: 18, biaya: 15, jalur: Daftar (M_1, M_1, M_1, M_2) waktu: 18, biaya: 15, jalur: Daftar (M_2, M_1, M_1, M_1, M_1)
Yang menimbulkan pertanyaan bagaimana ini harus ditangani. Haruskah semua dicetak atau hanya satu? Dan bagaimana jika waktunya akan berbeda? Apakah satu dengan biaya terendah dan tidak ada tenggat waktu yang terlewat atau haruskah itu juga dengan waktu terendah?
sumber
O(m^n)
waktu. Iterasi setiap mesin untuk semua tugas membutuhkanO(n*m^n)
waktu.O(n*m^n)
mengulangi setiap tugas untuk masing-masing jalur? Dan mengulangi setiap mesin seperti untuk setiap tugasO(n*m)
.O(n*m^n)
".O(m*m^n)=O(m^n+1)
. Namun, skornya masih sama.