?
Solved

File Backup

Posted on 1997-03-17
1
Medium Priority
?
149 Views
Last Modified: 2010-04-04
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.
0
Comment
Question by:ericw
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
1 Comment
 
LVL 3

Accepted Solution

by:
sperling earned 200 total points
ID: 1334771
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

Featured Post

[Webinar] Lessons on Recovering from Petya

Skyport is working hard to help customers recover from recent attacks, like the Petya worm. This work has brought to light some important lessons. New malware attacks like this can take down your entire environment. Learn from others mistakes on how to prevent Petya like worms.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

The uses clause is one of those things that just tends to grow and grow. Most of the time this is in the main form, as it's from this form that all others are called. If you have a big application (including many forms), the uses clause in the in…
In my programming career I have only very rarely run into situations where operator overloading would be of any use in my work.  Normally those situations involved math with either overly large numbers (hundreds of thousands of digits or accuracy re…
In this video we outline the Physical Segments view of NetCrunch network monitor. By following this brief how-to video, you will be able to learn how NetCrunch visualizes your network, how granular is the information collected, as well as where to f…
NetCrunch network monitor is a highly extensive platform for network monitoring and alert generation. In this video you'll see a live demo of NetCrunch with most notable features explained in a walk-through manner. You'll also get to know the philos…
Suggested Courses
Course of the Month10 days, 12 hours left to enroll

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question