interesting, multi-knapsack problem. Some heuristics sort all of the files and take all of the largest until it exceeds disk size. (one less than that)
Largest remaining file that will fit might be good enough. But an improvement. for the remaining (still sorted) files take (3 +/\ ]) running total, and the average/median of these. remove the last files from your bin, until remaining space exceeds that total, then pick the closest contiguous triplet from remaining files as your starting point. set 'j k l' =. start indices while. not in threshold of say 1kb do. if. over do. l=.l+1 if. stillover do. k=.k+1 end. end. if. under do. j=.j-1 if. stilunder do. k=.k-1 end. end. end. taking as many large files as possible in the first disks makes packing the next disks easier. ----- Original Message ----- From: Devon McCormick <devon...@gmail.com> To: J-programming forum <programm...@jsoftware.com> Sent: Friday, May 20, 2016 10:35 PM Subject: Re: [Jprogramming] Even partitions I don't care about the number of files, only the total size per partition. What Pascal suggested was my initial idea - it's probably good enough. Another ideas is to generate a lot of random partitions and pick the best one but I think Raul points up what's missing from the problem statement: a measure of how good a solution is. I don't see how this is like ensuring that fractional portions sum to 100%. My idea is more to divide up files I want to back up onto a medium with a specific capacity, like a writeable DVD, assuming the sum total is such that an even number of discs should suffice. Anyway, I'll try a couple of these ideas and see how they work. Thanks for everyone's input. On Fri, May 20, 2016 at 10:27 PM, Don Guinn <dongu...@gmail.com> wrote: > Sounds like making sure that percentages add to 100%. Why people check that > is curious. > On May 20, 2016 1:11 PM, "'Pascal Jasmin' via Programming" < > programm...@jsoftware.com> wrote: > > > Do you want an almost equal number of files in each group as well? > > > > A quick approach is to randomly split the files into groups, then > > repeatedly take a large file out of a too big group, and place it into a > > too small group. The average/target group size is quickly calculated. > > > > Also take a small file out of a too long group, and place it into a too > > short group. > > > > > > > > > > ----- Original Message ----- > > From: Devon McCormick <devon...@gmail.com> > > To: J-programming forum <programm...@jsoftware.com> > > Sent: Friday, May 20, 2016 1:37 PM > > Subject: Re: [Jprogramming] Even partitions > > > > It's an arbitrary grouping so that the sum of file sizes in each group is > > nearly equal between groups. To roughly approximate a distribution, you > > could use something like this: > > szs=. (+/16 4000?@$400) + (+/8 4000?@$2e3) + (+/4 4000?@$5e5) + > 4000?@$1e6 > > On May 20, 2016 10:48 AM, "David Porter" <dpor...@cissoid.net> wrote: > > > > > Groups based on what? > > > > > > Dave > > > On 5/20/2016 10:11 AM, Devon McCormick wrote: > > > > > >> I have a few thousand photos I want to put into a small number of > groups > > >> as > > >> equally-sized as possible. It looks like a knapsack problem but I > only > > >> need to get within some tolerant equality. > > >> > > >> Has anyone done something like this? > > >> > > >> Thanks, > > >> > > >> Devon > > >> ---------------------------------------------------------------------- > > >> For information about J forums see > http://www.jsoftware.com/forums.htm > > > > >> > > > > > > ---------------------------------------------------------------------- > > > For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Devon McCormick, CFA Quantitative Consultant ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
