Eu tenho um monte de arquivos de mídia que eu quero gravar em DVD, mas desde que cada DVD só se encaixa 4.5GB, eu tenho que encontrar a melhor maneira de organizar os arquivos para usar o número mínimo de DVDs (caso contrário, o espaço vazio esquerda em cada DVD pode facilmente adicionar). Há alguma ferramenta para ajudar nisso?
Muitos anos atrás, havia um utilitário DOS para fazer isso com disquetes.
Experimente o Span de DVD gratuito:
DVD Span is a backup tool for writing the contents of large folders to multiple DVDs. DVD Span can automatically determine the best organization of each disk in order to fit the maximum amount of data on the minimum number of disks. DVDSpan is a great tool for backing up your music collection, photos, or even your entire hard disk to DVDs. And because it produces regular DVDs (or CDs), no special software is required to read or restore your backups.
Ah, o problema da mochila . Eu só encontrei um solucionador online para isso, aqui . Seu tamanho de mochila seria de 4,5 GB e cada pacote seria seu tamanho de arquivo. Você precisará massagear sua saída um pouco para adequar-se à sua aplicação específica, mas ela deve ser viável. Isso não vai correr muito rápido, porque esse problema é difícil .
A resposta de Jeff Shattock está correta de que isso é equivalente (ou isomórfico, como os matemáticos escrevem) a um problema de otimização combinatória, mas é equivalente ao 1-dimensional problema de empacotamento de bin , não o problema de mochila .
Para sua sorte, eu tenho alguns códigos para compartilhar que resolverão este problema para você, ou qualquer outra pessoa, com acesso a um computador Windows com pelo menos a versão 3.5 do .NET Framework instalado.
Primeiro, baixe e instale o LINQPad .
Em segundo lugar, baixe a consulta LINQPad que acabei de escreveu - aqui está o linq (ha) para o arquivo raw. Salve como um arquivo .linq e abra-o no LINQPad.
Altere os parâmetros:
Aqui está a parte do código de consulta do LINQPad que você deve alterar:
int binSizeMb = 4476; // This is the (floor of the) total size of a DVD+R reported by CDBurnerXP.
string rootFileFolderPath = @"F:06 - Polyester Pimpstrap Intergalactic Extravaganza multicam";
Altere binSizeMb para o tamanho do seu 'bin', por ex. CD, DVD, ex. int binSizeMb = 650; para um CD.
Observação - o valor binSizeMb é interpretado como o que às vezes é chamado de mebibyte . Ao contrário da minha infância, quando todos os múltiplos de byte eram 'binários', às vezes 'MB' agora se refere a 'megabyte decimal' ou exatamente 1.000.000 bytes, ao contrário dos 1.048.576 bytes de um mebibyte (MiB), que são usados no meu código . Se você quiser mudar isso, altere a linha const int bytesPerMb = 1048576; no código para const int bytesPerMb = 1000000; .
Altere rootFileFolderPath para o caminho completo da pasta que contém os arquivos que você deseja 'empacotar em caixas', ex. string rootFileFolderPath = @"C:\MySecretBinFilesFolder"; .
Execute a consulta pressionando F5 ou clicando no botão Executar no canto superior esquerdo da guia de consulta.
O código de consulta irá enumerar todos os arquivos na pasta rootFileFolderPath , de forma recursiva, o que significa que incluirá arquivos em todas as subpastas também.
Em seguida, ele criará 'escaninhos' para os arquivos, de modo que o tamanho total de todos os arquivos em cada escaninho seja menor ou igual ao tamanho do escaninho especificado.
No painel de resultados do LINQPad, você verá duas listas.
A primeira lista é de todos os arquivos encontrados, listados em ordem decrescente de tamanho.
A segunda lista são os escaninhos criados por "empacotando os arquivos", com uma lista dos arquivos e seus tamanhos, bem como o tamanho restante do escaninho.
Aqui está uma captura de tela mostrando a segunda lista e as duas primeiras caixas criadas:
DeacordocomaWikipedia,oalgoritmoqueusei-aestratégiaFirstFitDecreasing(FFD)-nãodeveriasertãoruim;EstadosdaWikipédia:
In2007,itwasproventhatthebound11/9OPT+6/9forFFDistight.
'OPT'refere-seàestratégiaótima(comoalgopotencialmenteinacessível,nãoumaestratégiarealemparticular).
Combasenasminhasmemóriasumtantoconfusasdostermosmatemáticosenvolvidos,issodevesignificarqueaestratégiaFFDdeve,napiordashipóteses,embalaritensem~1,22vezesonúmerodecaixasqueumaestratégiaótimafaria.Portanto,essaestratégiapodeagruparitensem5posiçõesaoinvésde4.Suspeitoqueodesempenhoprovavelmenteestejamuitopróximodoideal,excetoparatamanhosdeitens'patológicos'específicos.
OmesmoartigodaWikipediatambémafirmaqueexisteum
Você poderia usar qualquer ferramenta de compactação que permita a divisão de um arquivo que eu acho
Você pode pegar uma das variantes do programa em Guia do Hitchhiker para Haskell , talvez depois de trabalhar em alguma parte de esse tutorial; o tutorial é escrito para resolver exatamente o seu problema de distribuir coisas em vários discos, por meio dos quais a solução é incrementalmente refinada, como exemplificado pela seguinte passagem de Capítulo 3 do tutorial:
Enough preliminaries already. let's go pack some CDs.
As you might already have recognized, our problem is a classical one. It is called a "knapsack problem" (google it up, if you don't know already what it is. There are more than 100000 links).
let's start from the greedy solution...
Aqui está uma pergunta semelhante (embora não seja a mesma: não está sendo solicitada otimização lá), onde você pode encontrar soluções / programas mais úteis para sua tarefa (se forem postados):
Em geral, o código Haskell é bastante expressivo (já que o Haskell é uma linguagem para programação em um alto nível de abstração) e, portanto, pode ser facilmente captado.
Ao olhar para o código de uma das soluções, lembre-se que a estrutura de nível superior do programa que queremos escrever é bastante simples, como colocado em Capítulo 1 do tutorial:
Now let's think for a moment about how our program will operate and express it in pseudocode:
main = Read list of directories and their sizes. Decide how to fit them on CD-Rs. Print solution.Sounds reasonable? I thought so.
Let's simplify our life a little and assume for now that we will compute directory sizes somewhere outside our program (for example, with "
du -sb *") and read this information from stdin.
e observe mais de perto as partes da solução.
Há séculos, escrevi o script PHP para executar essa tarefa: link
Além disso, experimente Discfit, que seleciona arquivos e diretórios para copiar em vários discos:
Tags performance media dvd burning algorithm