Utilitas untuk mendistribusikan file secara optimal ke beberapa DVD?

Saya memiliki banyak file media yang ingin saya rekam ke DVD, tetapi karena setiap DVD hanya sesuai dengan 4,5GB, saya harus menemukan cara optimal untuk mengatur file untuk menggunakan jumlah minimum DVD (jika tidak, ruang kosong tersisa di setiap DVD dapat dengan mudah ditambahkan). Apakah ada alat untuk membantu ini?

Bertahun-tahun yang lalu ada utilitas DOS untuk melakukan ini dengan floppy disk.

Coba Rentang DVD gratis :

DVD Span adalah alat cadangan untuk menulis konten folder besar ke banyak DVD. DVD Span dapat secara otomatis menentukan pengaturan terbaik dari setiap disk agar sesuai dengan jumlah maksimum data pada jumlah minimum disk. DVDSpan adalah alat yang hebat untuk membuat cadangan koleksi musik Anda, foto, atau bahkan seluruh hard disk Anda ke DVD. Dan karena ini menghasilkan DVD (atau CD) biasa, tidak ada perangkat lunak khusus yang diperlukan untuk membaca atau memulihkan cadangan Anda.

Ah, masalah ransel . Saya hanya dapat menemukan satu pemecah online untuk ini, di sini . Ukuran ransel Anda adalah 4,5GB, dan setiap paket adalah ukuran file Anda. Anda harus memijat outputnya sedikit agar sesuai dengan aplikasi khusus Anda, tetapi harus bisa diterapkan. Ini tidak akan berjalan sangat cepat, karena masalah ini sulit .

Gambaran

Jawaban Jeff Shattock benar bahwa ini setara (atau isomorfik, seperti yang ditulis matematikawan) untuk masalah optimisasi kombinatorial, tetapi sama dengan masalah pengemasan bin 1 dimensi , bukan masalah ransel .

Beruntung bagi Anda, saya memiliki beberapa kode untuk dibagikan yang akan menyelesaikan masalah ini untuk Anda, atau siapa pun, dengan akses ke komputer Windows dengan setidaknya versi 3.5 dari .NET Framework diinstal.

Solusi Kasar

1. Pertama, unduh dan instal LINQPad .

2. Kedua, unduh kueri LINQPad yang baru saja saya tulis - inilah linq (ha) ke file mentah. Simpan sebagai file .linq dan buka di LINQPad.

3. Ubah parameter:

   Inilah bagian dalam kode kueri LINQPad yang harus Anda ubah:

   int binSizeMb = 4476; // This is the (floor of the) total size of a DVD+R reported by CDBurnerXP. string rootFileFolderPath = @"F:\2006 - Polyester Pimpstrap Intergalactic Extravaganza multicam";

   Ubah binSizeMbke ukuran 'tempat sampah' Anda, mis. CD, DVD, mis. int binSizeMb = 650;untuk CD.

   Catatan - binSizeMbnilai ditafsirkan sebagai apa yang kadang-kadang disebut sebagai mebibyte . Berlawanan dengan masa kecil saya, ketika semua kelipatan byte adalah 'biner', kadang-kadang 'MB' sekarang merujuk pada 'megabita desimal' atau tepatnya 1.000.000 byte, berbeda dengan 1.048.576 byte dari mebibyte (MiB), yang digunakan dalam kode saya . Jika Anda ingin mengubah ini, ubah baris const int bytesPerMb = 1048576;dalam kode menjadi const int bytesPerMb = 1000000;.

   Ubah rootFileFolderPathke path lengkap folder yang berisi file yang ingin Anda 'masukkan ke dalam bins', mis. string rootFileFolderPath = @"C:\MySecretBinFilesFolder";.

4. Jalankan kueri dengan menekan F5atau mengklik tombol Execute di kiri atas tab kueri.

Hasil

Kode permintaan akan menyebutkan semua file dalam rootFileFolderPathfolder, secara rekursif, yang berarti akan menyertakan file di semua subfolder juga.

Maka itu akan membuat 'sampah' untuk file sehingga ukuran total semua file di setiap bin kurang dari atau sama dengan ukuran bin yang ditentukan.

Di panel hasil LINQPad Anda akan melihat dua daftar.

Daftar pertama adalah dari semua file yang ditemukannya, terdaftar dalam urutan menurun berdasarkan ukuran.

Daftar kedua adalah tempat sampah yang dibuat dengan 'mengemas file', dengan daftar file dan ukurannya, serta ukuran sampah yang tersisa.

Berikut screenshot yang menunjukkan daftar kedua dan dua nampan pertama dibuat:

Analisis Sepintas

Menurut Wikipedia, algoritma yang saya gunakan - strategi First Fit Decreasing (FFD) - tidak boleh terlalu buruk; Negara Wikipedia:

Pada 2007, terbukti bahwa 11/9 OPT + 6/9 terikat untuk FFD ketat.

'OPT' mengacu pada strategi optimal (sebagai sesuatu yang berpotensi tidak dapat dijangkau, bukan strategi aktual tertentu).

Berdasarkan ingatan saya yang agak kabur dari istilah matematika yang terlibat, ini harus berarti bahwa strategi FFD harus, paling buruk, mengemas item menjadi ~ 1,22 kali jumlah tempat sampah yang strategi optimal akan. Jadi, strategi ini mungkin mengemas item menjadi 5 nampan bukan 4. Saya curiga kinerjanya cenderung sangat dekat dengan yang optimal kecuali untuk ukuran item 'patologis' tertentu.

Artikel Wikipedia yang sama juga menyatakan bahwa ada "algoritma yang tepat" . Saya mungkin memutuskan untuk mengimplementasikannya juga. Saya harus membaca makalah yang menjelaskan algoritma terlebih dahulu.

Anda bisa menggunakan alat kompresi yang memungkinkan pemisahan arsip saya pikir

Anda dapat mengambil salah satu varian program dalam panduan Hitchhiker untuk Haskell , mungkin setelah mengerjakan beberapa bagian dari tutorial itu; tutorial ini ditulis untuk menyelesaikan masalah Anda yang sebenarnya dalam mendistribusikan berbagai hal ke beberapa disk yang solusinya disempurnakan secara bertahap, sebagaimana dicontohkan oleh bagian berikut dari Bab 3 tutorial ini:

Pendahuluan sudah cukup. ayo kita berkemas beberapa CD.

Seperti yang mungkin sudah Anda ketahui, masalah kami adalah masalah klasik. Ini disebut "masalah ransel" ( google it up , jika Anda belum tahu apa itu. Ada lebih dari 100.000 tautan).

mari kita mulai dari solusi serakah ...

Lebih banyak ide: pertanyaan terkait

Berikut adalah pertanyaan serupa (walaupun tidak sama: itu tidak diminta untuk optimasi di sana), di mana Anda dapat menemukan solusi / program yang lebih berguna untuk tugas Anda (jika akan diposting):

• /unix//q/10158/4319 - "Memecah pohon direktori besar menjadi potongan ukuran tertentu?"

Beberapa petunjuk untuk memahami pemrograman dalam tutorial yang disarankan

Secara umum, kode Haskell cukup ekspresif (karena Haskell adalah bahasa pemrograman pada abstraksi tingkat tinggi), dan karenanya dapat dengan mudah dipahami.

Ketika melihat kode dari salah satu solusi, ingatlah bahwa struktur tingkat atas dari program yang ingin kita tulis cukup sederhana, seperti yang dijelaskan di Bab 1 tutorial ini:

Sekarang mari kita berpikir sejenak tentang bagaimana program kami akan beroperasi dan mengekspresikannya dalam pseudocode:

main = Read list of directories and their sizes.
       Decide how to fit them on CD-Rs.
       Print solution.

Kedengarannya masuk akal? Saya pikir juga begitu.

Mari kita sederhanakan sedikit kehidupan kita dan berasumsi untuk sekarang bahwa kita akan menghitung ukuran direktori di suatu tempat di luar program kita (misalnya, dengan " du -sb *") dan membaca informasi ini dari stdin.

dan melihat lebih dekat pada bagian-bagian dari solusi.

Beberapa waktu yang lalu saya menulis skrip PHP untuk melakukan tugas seperti itu: https://bitbucket.org/borszczuk/php-backup-maker/

Coba juga Discfit, yang memilih file dan direktori untuk disalin ke berbagai disk:

https://sourceforge.net/projects/discfit/