Utilitário para otimizar a distribuição de arquivos em vários DVDs?

Tenho vários arquivos de mídia que quero gravar em DVD, mas como cada DVD cabe apenas 4,5 GB, tenho que encontrar a maneira ideal de organizar os arquivos para usar o número mínimo de DVDs (caso contrário, o espaço vazio deixado em cada DVD pode adicionar facilmente). Existem ferramentas para ajudar nisso?

Muitos anos atrás, havia um utilitário DOS para fazer isso com disquetes.

Experimente o DVD Span gratuito :

O DVD Span é uma ferramenta de backup para gravar o conteúdo de pastas grandes em vários DVDs. O DVD Span pode determinar automaticamente a melhor organização de cada disco para ajustar a quantidade máxima de dados no número mínimo de discos. O DVDSpan é uma ótima ferramenta para fazer backup de sua coleção de músicas, fotos ou mesmo todo o seu disco rígido em DVDs. E como produz DVDs (ou CDs) regulares, nenhum software especial é necessário para ler ou restaurar seus backups.

Ah, o problema da mochila . Só consegui encontrar um solucionador online para isso, aqui . O tamanho da sua mochila seria 4,5 GB e cada pacote teria o tamanho do seu arquivo. Você precisará massagear sua saída um pouco para se ajustar ao seu aplicativo em particular, mas deve ser viável. Isso não será executado muito rápido, porque esse problema é difícil .

visão global

A resposta de Jeff Shattock está correta: isso é equivalente (ou isomórfico, como matemáticos escrevem) a um problema de otimização combinatória, mas é equivalente ao problema de empacotamento de lixeira unidimensional , não ao problema da mochila .

Para sua sorte, tenho um código para compartilhar que resolverá esse problema para você ou qualquer outra pessoa, com acesso a um computador Windows com pelo menos a versão 3.5 do .NET Framework instalada.

Uma solução difícil

1. Primeiro, baixe e instale o LINQPad .

2. Segundo, baixe a consulta LINQPad que acabei de escrever - aqui está o linq (ha) no arquivo bruto. Salve-o como um arquivo .linq e abra-o no LINQPad.

3. Mude os parâmetros:

   Aqui está a parte do código da consulta 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:\2006 - Polyester Pimpstrap Intergalactic Extravaganza multicam";

   Mude binSizeMbpara o tamanho da sua 'lixeira', por exemplo, CD, DVD, ex. int binSizeMb = 650;para um CD.

   Nota - o binSizeMbvalor é interpretado como às vezes chamado de mebibyte . Ao contrário da minha infância, quando todos os múltiplos de bytes eram 'binários', às vezes 'MB' agora se refere a um 'megabyte decimal' ou exatamente 1.000.000 de bytes, em oposição aos 1.048.576 bytes de um mebibyte (MiB), usado no meu código . Se você deseja alterar isso, altere a linha const int bytesPerMb = 1048576;no código para const int bytesPerMb = 1000000;.

   Mude rootFileFolderPathpara o caminho completo da pasta que contém os arquivos que você deseja 'empacotar em compartimentos', ex. string rootFileFolderPath = @"C:\MySecretBinFilesFolder";.

4. Execute a consulta pressionando F5ou clicando no botão Executar na parte superior esquerda da guia de consulta.

Resultados

O código da consulta enumerará todos os arquivos da rootFileFolderPathpasta, recursivamente, o que significa que também incluirá arquivos em todas as subpastas.

Em seguida, ele criará 'compartimentos' para os arquivos, de modo que o tamanho total de todos os arquivos em cada compartimento seja menor ou igual ao tamanho 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 compartimentos criados por 'empacotar os arquivos', com uma lista dos arquivos e seus tamanhos, bem como o tamanho restante do compartimento.

Aqui está uma captura de tela mostrando a segunda lista e os dois primeiros compartimentos criados:

Análise Curricular

De acordo com a Wikipedia, o algoritmo que eu usei - a estratégia First Fit Decreasing (FFD) - não deve ser tão ruim; A Wikipedia afirma:

Em 2007, foi comprovado que o limite de 11/9 OPT + 6/9 para FFD é apertado.

'OPT' refere-se à estratégia ideal (como algo potencialmente inacessível, e não uma estratégia real em particular).

Com base nas minhas memórias um tanto confusas dos termos matemáticos envolvidos, isso deve significar que a estratégia do FFD deve, na pior das hipóteses, empacotar itens em ~ 1,22 vezes o número de caixas que uma estratégia ideal faria. Portanto, essa estratégia pode empacotar itens em 5 compartimentos em vez de 4. Suspeito que seu desempenho provavelmente esteja muito próximo do ideal, exceto por tamanhos específicos de itens 'patológicos'.

O mesmo artigo da Wikipedia também afirma que existe um "algoritmo exato" . Eu também posso decidir implementar isso. Vou ter que ler o artigo que descreve o algoritmo primeiro.

Você poderia usar qualquer ferramenta de compressão que permita dividir um arquivo, eu acho

Você pode usar uma das variantes do programa no guia do Hitchhiker para Haskell , talvez depois de trabalhar em alguma parte desse tutorial; o tutorial é escrito para solucionar exatamente o seu problema de distribuir itens em vários discos, nos quais a solução é refinada de forma incremental, como exemplificado pela seguinte passagem do Capítulo 3 do tutorial:

Já chega de preliminares. vamos embalar alguns CDs.

Como você já deve ter reconhecido, nosso problema é clássico. É chamado de "problema da mochila" ( pesquise no Google , se você ainda não sabe o que é. Existem mais de 100000 links).

vamos começar com a solução gananciosa ...

Mais idéias: uma pergunta relacionada

Aqui está uma pergunta semelhante (embora não seja a mesma: não está sendo solicitada otimização), onde você pode encontrar soluções / programas mais úteis para a sua tarefa (se eles forem publicados):

• /unix//q/10158/4319 - "Dividindo uma árvore de diretório grande em pedaços de tamanho especificado?"

Algumas dicas para entender a programação no tutorial sugerido

Em geral, o código Haskell é bastante expressivo (já que Haskell é uma linguagem para programação em um alto nível de abstração) e, portanto, pode ser facilmente compreendido.

Ao analisar o código de uma das soluções, lembre-se de que a estrutura de nível superior do programa que queremos escrever é bastante simples, como mostra o Capítulo 1 do tutorial:

Agora, vamos pensar por um momento sobre como nosso programa funcionará e expressá-lo em pseudocódigo:

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

Parece razoável? Eu pensei assim.

Vamos simplificar um pouco nossa vida e supor, por enquanto, que calcularemos o tamanho dos diretórios em algum lugar fora do nosso programa (por exemplo, com " du -sb *") e leremos essas informações no stdin.

e observe mais de perto as partes da solução.

Idades atrás eu escrevi o script PHP para fazer essa tarefa: https://bitbucket.org/borszczuk/php-backup-maker/

Além disso, tente o Discfit, que seleciona arquivos e diretórios para copiar em vários discos:

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