File Backup

How does one go about calculating the minimum number of floppy disks required to backup a given list of files? I believe this is called the 'KnapSack' problem, but I've never managed to find someone who's solved it.
ericwAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

sperlingCommented:
Hmmm... I've solved it. And so has others i know... However, a few assumptations must ofcourse be made.


Okie. Assumptations are as follows:
You have a list of files, and ofcourse the sizes in bytes of each file.
You know what kind of floppies will be used, and all floppies are equal.
AND, the floppies ain't formatted in some weird format.
Standard floppy format uses a block size of 512 bytes.

I'll just pretend all files are smaller than the available space on one floppy. If you need to split files, filling up the floppies ain't a problem.


Calculate number of blocks on floppy, by taking size of an empty floppy and divide by 512

Take all the file sizes. If they are not dividable by 512, increase their sizes until they are.

Divide all sizes by 512 and store these values as the file sizes. Sort the filelist based on size, largest files first

Here's some pseudo-code:

FileToTest := First file
FloppyCount := 0
repeat
  Increase floppy count
  FloppyUsed := 0
  repeat
    if Size of file (FileToTest) <= Available on current floppy
      Increase FloppyUsed with size of file FileToTest
      Remove file FileToTest from filelist
    else
      Increase FileToTest
  until (FileToTest = last file) or (Floppy is full) or (No more files)

 

  FileToTest := first file
  FloppyUsed := 0
until No more files

If last floppy is empty
  Decrease FloppyCount


This code *will* fill up the floppies, although it doesn't necessarily seem so at first glance.


Regards,

Erik.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Delphi

From novice to tech pro — start learning today.