Solved

File Backup

Posted on 1997-03-17
1
143 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
1 Comment
 
LVL 3

Accepted Solution

by:
sperling earned 100 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

This article explains how to create forms/units independent of other forms/units object names in a delphi project. Have you ever created a form for user input in a Delphi project and then had the need to have that same form in a other Delphi proj…
Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small print…
This Micro Tutorial hows how you can integrate  Mac OSX to a Windows Active Directory Domain. Apple has made it easy to allow users to bind their macs to a windows domain with relative ease. The following video show how to bind OSX Mavericks to …
As a trusted technology advisor to your customers you are likely getting the daily question of, ‘should I put this in the cloud?’ As customer demands for cloud services increases, companies will see a shift from traditional buying patterns to new…

910 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

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now