1 reply to this topic

[R.Bon]

Boa noite pessoal!
Por favor, será que alguém aqui poderia me auxiliar com um um certo algoritmo ?
Seguinte: a idéia é otimizar a gravação de arquivos em cd/dvd (em termos de aproveitamento de espaço).
Costumo arquivar os arquivos que baixo da net em dvd, e geralmente são arquivos de algumas centenas de Mb ou pouco mais de 1Gb. Dependendo das combinações, consigo gravar 3, 4, às vezes 5 arquivos em um dvd de 4.7Gb.
Na hora de preparar os grupos para gravação, eu faço uma listagem do que quero gravar usando o "Directory Lister" e lanço os nomes dos arquivos com seus tamanhos (em Gb) numa planilha. Depois vou tentando combinar os arquivos de forma que o tamanho total fique em 4.38Gb (que é o que realmente dá pra gravar no dvd).
A título de curiosidade: esses dias agrupei 42 arquivos de forma que possa gravá-los em 12 dvds. Trabalhei separando os conjuntos em 4.38Gb (como eu disse, deu uma média de 3 arquivos por dvd, alguns com 4, outros com 5) mas no sexto dvd ficou passando pouco mais de 1Mb e não teve overburning que me ajudasse...
Talvez já esteja claro o que preciso, mas lá vai o que pensei:
- crio uma matriz e atribuo o tamanho de cada arquivo que quero gravar aos seus elementos;
- ordeno pelo tamanho e tento agrupar, a partir do arquivo maior, grupos de 4.37Gb (melhor deixar essa folguinha...);
Até aqui é o que eu venho fazendo na planilha (LibreOffice), porém dá pra imaginar o tempo que perco copiando e colando os tamanhos dos arquivos nas células... deixo uma célula dando o resultado da soma e outra com o que falta para 4.37Gb, assim sei quanto está dando minha compilação e sei que tamanho de arquivo preciso colocar para alcançar meu limite. Problema é que posso estar perdendo muitos casos "ótimos", digo, de repente nesse meu processo precário eu posso até ir encontrando as combinações que me ajudam, mas além do enorme desperdício de tempo eu posso não encontrar combinações que podem fazer que no final eu tenha que gravar menos dvds (para o caso que não estar conseguindo formar grupos de exatos 4.37Gb ou próximo disso, já que o fator "sorte" entra em jogo pois eu poderia estar com 200 arquivos de 2Gb pra gravar e daí não tem choro: teria que gravar somente 2 por dvd, perdendo quase 500Mb por mídia. Óbvio).
Ah sim: dividir os arquivos em volumes não é uma opção. Quero gravá-los em arquivo único, tal como são.
Eu não consigo provar que o que vou dizer é verdadeiro (tampouco falso), mas mesmo que eu consiga (pelo meu "método visual") agrupar 30 arquivos em 10 compilações, não quer dizer que é somente isso que pode ser feito, digo, pode ser que seria possível agrupar em 9 compilações, mesmo que sobre algum arquivo mas a perda de espaço em cada dvd gravado seja menor e compense deixar um pra gravar depois...
Será que deu pra entender?...
Ah sim: não faço idéia de como elaborar um algoritmo pra ir formando as combinações de n elementos até dar 4.37Gb, sendo que preciso testar os mesmos valores para um sem número de combinações, pois "casos vencedores" não podem ser separados sem que eu saiba que ao final terei o menor número de grupos com 4.37Gb...
Muito obrigado!

[Moço da Padaria]

Pois bem... Eu faria assim:

1. Criaria uma matriz com a identificação do arquivo, e seu tamanho real.

2. Popularia a matriz com os dados de todos os arquivos. (Em qual linguagem vc vai fazer? Shell?)

3. Ordenaria os valores, do maior tamanho de arquivo para o menor.

4. Sabendo o tamanho máximo que cabe em cada DVD, colocaria o maior arquivo nele. Sabendo agora o espaco restante, colocaria agora o segundo maior arquivo (que caiba no espaco restante). Se o segundo valor da matriz nao couber, vou para o terceiro, quarto.... assim por diante.

5. Colocarei os arquivos que couberem, até não haver mais arquivos na matriz que caibam na mídia. Sempre que colocar um arquivo no dvd, removo da matriz (ou marco com uma flag, algo assim...).

6. Estando o primeiro DVD cheio, vou para o segundo, e assim por diante. Sempre usando a mesma lógica



Problema resolvido