I do exactly the same thing, using proprietary code (sorry, can't share it). However, I use some key non-proprietary code which I can point you to: Filesys::DiskUsage to determine the size of a directory. Note that sector sizes on CDs are generally 1024 bytes, which doesn't match what du will tell you, but Filesys::DiskUsage can take parameters that allow you to specify what blocksize to assume.

For my case, I need directories to show up on the CD in a particular order, which means that if dir5 can fit on disk1, but dir4 can't, then I can't put dir5 on disk1 in dir4's place. That may not be true for you. For me, it means that I may use more CDs, but I avoid the knapsack problem. You may need to look that problem up if you want to minimise the number of CDs that you need.

If you are minimising, all you need to do is use Filesys::DiskUsage to get the sizes of each directory, then you can sort the directories in memory using those numbers until you get your solution. Then you can copy the directories around - I often use tar for copying directory structures which makes things much easier when you're dealing with many files, especially if some are symlinks and the like.