Утилита для оптимального распределения файлов на несколько DVD?

Попробуйте бесплатный DVD Span :

DVD Span - это инструмент резервного копирования для записи содержимого больших папок на несколько DVD. DVD Span может автоматически определять наилучшую организацию каждого диска, чтобы соответствовать максимальному объему данных на минимальном количестве дисков. DVDSpan - отличный инструмент для резервного копирования музыкальной коллекции, фотографий или даже всего жесткого диска на DVD. А поскольку он производит обычные DVD-диски (или компакт-диски), не требуется никакого специального программного обеспечения для чтения или восстановления ваших резервных копий.

Ах, проблема с рюкзаком . Я мог бы найти только один онлайн решатель для этого здесь . Ваш размер рюкзака будет 4,5 ГБ, а каждый пакет будет соответствовать размеру вашего файла. Вам нужно будет немного помассировать его вывод, чтобы он соответствовал вашему конкретному применению, но это должно быть работоспособно. Это не будет работать очень быстро, потому что эта проблема сложная .

Overview

Jeff Shattock's answer is correct that this is equivalent (or isomorphic, as mathematicians write) to a combinatorial optimization problem, but it's equivalent to the 1-dimensional bin packing problem, not the knapsack problem.

Lucky for you, I have some code to share that will solve this problem for you, or anyone else, with access to a Windows computer with at least version 3.5 of the .NET Framework installed.

A Rough Solution

1. First, download and install LINQPad.

2. Second, download the LINQPad query I just wrote – here's the linq (ha) to the raw file. Save it as a .linq file and open it in LINQPad.

3. Change the parameters:

   Here's the part in the LINQPad query code you should change:

   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";

   Change binSizeMb to the size of your 'bin', e.g. CD, DVD, ex. int binSizeMb = 650; for a CD.

   Note – the binSizeMb value is interpreted as what's sometimes referred to as a mebibyte. Contrary to my childhood, when all byte multiples were 'binary', sometimes 'MB' now refers to a 'decimal megabyte' or exactly 1,000,000 bytes, as opposed to the 1,048,576 bytes of a mebibyte (MiB), which is used in my code. If you wish to change this, change the line const int bytesPerMb = 1048576; in the code to const int bytesPerMb = 1000000;.

   Change rootFileFolderPath to the full path of the folder containing the files you wish to 'pack into bins', ex. string rootFileFolderPath = @"C:\MySecretBinFilesFolder";.

4. Run the query by either hitting F5 or clicking the Execute button at the top left of the query tab.

Results

The query code will enumerate all of the files in the rootFileFolderPath folder, recursively, meaning it will include files in all of the subfolders too.

Then it will create 'bins' for the files such that the total size of all the files in each bin is less than or equal to the bin size specified.

In the LINQPad results pane you'll see two lists.

The first list is of all the files it found, listed in decreasing order by size.

The second list is the bins created by 'packing the files', with a list of the files and their sizes, as well as the remaining size of the bin.

Here's a screenshot showing the second list and the first two bins created:

Cursory Analysis

According to Wikipedia, the algorithm I used – the First Fit Decreasing (FFD) strategy – shouldn't be too bad; Wikipedia states:

In 2007, it was proven that the bound 11/9 OPT + 6/9 for FFD is tight.

'OPT' refers to the optimal strategy (as something potentially unreachable, not any particular actual strategy).

Based on my somewhat fuzzy memories of the mathematical terms involved, this should mean that the FFD strategy should, at worst, pack items into ~1.22 times the number of bins that an optimal strategy would. So, this strategy might pack items into 5 bins instead of 4. I suspect that it's performance is likely to be very close to optimal except for specific 'pathological' item sizes.

The same Wikipedia article also states that there is an "exact algorithm". I may decide to implement that too. I'll have to read the paper that describes the algorithm first.

Я думаю, вы можете использовать любой инструмент сжатия, который позволяет разбить архив

You can take one of the variants of the program in Hitchhiker's guide to Haskell, perhaps after working through some part of that tutorial; the tutorial is written around solving exactly yours problem of distributing things onto several disks whereby the solution is incrementally refined, as exemplified by the following passage from Chapter 3 of the 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...

More ideas: a related question

Here is a similar question (although not the same: it's not being asked for optimization there), where you may find more useful solutions/programs for your task (if they will be posted):

• https://unix.stackexchange.com/q/10158/4319 -- "Splitting large directory tree into specified-size chunks?"

Some hints for understanding the programming in the suggested tutorial

In general, the Haskell code is quite expressive (since Haskell is a language for programming on a high level of abstraction), and hence can be easily grasped.

When looking at the code of one of the solutions, remember that the top-level structure of the program we want to write is quite simple, as put in Chapter 1 of the 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.

and look further more closely at the parts of the solution.

Много лет назад я написал PHP-скрипт для решения этой задачи: https://bitbucket.org/borszczuk/php-backup-maker/

Также попробуйте Discfit, которая выбирает файлы и каталоги для копирования на различные диски:

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