Алгоритмическая задача на объединение мелких файлов - C#
Формулировка задачи:
Добрый день!
Возникла такая алгоритмическая задачка.
В директории с программой лежит много мелких txt-файлов размером от 1 до 70 Мб. Необходимо:
1) объединить файлы таким образом, чтобы получились файлы в среднем по 50 Мб (не меньше). Новые файлы записываются в директорию "result".
2) названия файлов должны сохраняться. То есть, в один мелкий файл дописываем несколько других мелких, а его название остается тем же самым.
3) если файл превышает 50 Мб, то внутрь него не нужно дописывать, а просто переносим его в result.
Сложность в том, чтобы придумать алгоритм, который оптимально комбинирует рандомные файлы по размеру - чтобы в итоге получались файлы в среднем по 50 Мб. Буду благодарен за помощь!
Решение задачи: «Алгоритмическая задача на объединение мелких файлов»
textual
Листинг программы
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication212
{
class Program
{
static void Main(string[] args)
{
//генерируем "файлы"
var list = new List<File>();
var rnd = new Random();
for (int i = 0; i < 100;i++ )
{
list.Add(new File { Name = i + ".txt", Size = rnd.Next(1, 100) * 1000000 });
}
//создаем объединенные файлы и выводим
foreach(var subList in Solve(list, 50000000))
{
Console.WriteLine((subList.Sum(f=>f.Size) / 1000000) + " MB: " + string.Join("+", subList.Select(f=>f.Name)));
}
Console.ReadLine();
}
private static IEnumerable<List<File>> Solve(List<File> list, int targetSize)
{
//сортируем по убыванию размера
var ordered = list.OrderByDescending(f => f.Size).ToList();
var used = new HashSet<File>();
//перебираем
for(int i=0;i<ordered.Count;i++)
if (!used.Contains(ordered[i]))//еще не использовался?
{
var sumSize = ordered[i].Size;
var res = new List<File>();
res.Add(ordered[i]);
used.Add(ordered[i]);
//если файл меньше targetSize
if(sumSize < targetSize)
//добавляем файлы, пока суммарный размер меньше targetSize
for (int j = i + 1; j < ordered.Count; j++)
if(!used.Contains(ordered[j]))//еще не использовался?
if (sumSize + ordered[j].Size < targetSize)//если суммарно не превышаем нужный размер, добавляем
{
//добавялем файл
res.Add(ordered[j]);
used.Add(ordered[j]);
sumSize += ordered[j].Size;
}
yield return res;
}
}
}
class File
{
public string Name;
public int Size;
}
}