What I can't prove without a lot more thought is whether you're ever going to be off by more than a single disc, and what can't be proven at all is whether that's close enough for real world purposes. (Since what's "acceptable" in the real world has to do with how long you're willing to wait for an answer vs. how much you care about that extra disc, and other factors.) But just know that the greedy approach won't only be suboptimal in theory, but it will also, sometimes, bleed over into an actual difference.

Eimi Metamorphoumai,
Won't always work,...

What I didn't say explicitly, but was implied by my bullet points was that 1 disc is being added to account for perfect (or even near perfect fits). The knapsack problem is hard but we aren't trying to break encryption we are trying to save a few pennies on CDs. I don't think (though I could be wrong) that it will ever waste more than 1 disk. Too make matters more difficult, we aren't talking about a handful of files but more likely hundreds if not thousands. Let's say that the total size is an exact multiple of 1 CD. That means every single CD needs to be an exact match (which may not even be possible). Proving it can or can not might take a while (extreme sarcasm). Why not just go with a "good enough" solution?

Update 2008-11-26: It turns out that this heuristic approach can be is much as 11/9 OPT + 1 bin (according to bin packing). While my experience has been that 1 extra is all you will ever need, it is possible to need more.

Cheers - L~R

How about file sizes of ($bucketsize / 2) + 1. That would be the worst case scenerio, and would take N buckets (where N is the number of files).

Although the OP is not talking about files that large (350Mb PDF files are a little large :), your algorithm can fail in the case of worst case data.

Just for thought:

If it is for backup,
then spread the data,
and add an additional CD as the checksum CD unit

ie: Write a perl based CD RAID 5
then you could recover from a bad or missing CD...

how many CD burners/PC's do you have available ??

That would be the worst case scenerio, but I would not say that the algorithm would fail. It would be as accurate as already indicated. it would predict n+1 but in reality you would only need n.

Zero

MidLifeXis,
If each file is ($bucketsize / 2) + 1, it means only 1 file can fit per CD with either method so mine still only wastes the 1 extra CD. I am failing to see how your worst case scenario would make my solution use more than 1 extra CD?

Cheers - L~R

My issue is not that you are wasting too many CDs, my issue is that you are not estimating enough CDs.

Maybe I misunderstood you originally when you said ...

$buckets = ($total_size / 700) + 1

... but this code (I think) implements your code. The test is then run against a set of buckets to verify that the bucket estimation is, in fact, correct. In this worst case, the number of files should be the number of buckets (or within one).

sub numbuckets {

  my $numfiles = shift;
  my $cdsize = 700 * 1024 * 1024;

  my $total_size = (($cdsize / 2) + 1) * $numfiles;

  my $buckets = ($total_size / $cdsize) + 1;

  return $buckets;
}

printf("Bucket estimation of %d buckets is %s for %d files.\n",
       numbuckets($_),
       ($_ <= numbuckets($_)) ? "valid" : "not valid", 
       $_)
  foreach (0 .. 5);

__END__

# My output...
Bucket estimation of 1 buckets is valid for 0 files.
Bucket estimation of 1 buckets is valid for 1 files.
Bucket estimation of 2 buckets is valid for 2 files.
Bucket estimation of 2 buckets is not valid for 3 files.
Bucket estimation of 3 buckets is not valid for 4 files.
Bucket estimation of 3 buckets is not valid for 5 files.
[download]

The answer is somewhere between $numbuckets (or $numbuckets - 1) and $numfiles. Where in that range depends on how densely you can pack the files.

--MidLifeXis