Ok Guys I'm really stuck here,
I try to make an algorithm that tries to find the best combination of the same numeric values into different Numbers.
Let me give you an example: you have a 700MB CD and you have 30Files ranging from some kilobytes to 50MB. Now the algorithm has to find out which files to burn so that the least amount of unused space is left.
While I already developed and implemented 2 algorithms which both work fine on a small amount of elements but 16 Elements already take one implementation one hour to calculate while the other one does it in about 10 seconds but at the price of saving 65535 integer Values. Now if I wanted to calculate a List of 30 Elements I would need either to save about 1*10^10 integer Values or calculate for about a week.
I can't calculate what 1000 elements would take me because when I try I get Overflow Exceptions in my calculator.
And also until now I use recursive functions but I could replace it with an iterative one in the memory hungry program BUT if I wanted to save the values to a file I would need 4Gigs for the 30 Element Example.
So I hope you can help me with your leet programming skills because I am just to stupid to think of an algorithm that could run on my pc. I mean maybe there already is an algorithm for this programm but I just couldn't find it with google.
Name:
Anonymous2006-10-20 19:25
use java lol
Name:
Someawe2006-10-20 19:35
I did, and I want to try in C as well, maybe it's running multiple times faster
Name:
Anonymous2006-10-20 19:36
This is a type of 'knapsack problem' - I recommend you read up on those
Name:
Someawe2006-10-20 19:39
thanks a lot this looks like what I hoped for
Name:
Someawe2006-10-20 19:47
Ok the first thing I read about it only covered how to reach the exact amout of e.g. 700MB but not the nearest amount to 700MB but I'm gonna read a book about it tomorrow and see if it can help me. But thanks again for pointing me into the right direction
Name:
Anonymous2006-10-20 21:48
#!/usr/bin/perl
use strict;
use File::Basename;
use Fatal qw(open);
my $cursize = 0;
my $currentout = 0;
my $dvdsize = 4400000000;
open(FILE,'>',"filelist.$currentout");
while(<>) {
chomp($_);
my $file = $_;
my $size = (stat($file))[7];
if ($cursize + $size > $dvdsize) {
close(FILE);
$currentout++;
open(FILE,'>',"filelist.$currentout");
$cursize = 0;
}
print "$currentout,\t$file$/";
print FILE "$file$/";
$cursize += $size;
}
close(FILE);
Name:
Anonymous2006-10-20 21:48
You give that script either a list of files on the commandline or pipe in a filelist. It produces filelists. Non-optimal
chomp;
my $file = ; # WTF do I do here LOL! my
LOL!! Real programmers don't use it.
use strict;
LOLOLOLOLLOLOLLLLO!
use English and use Obfuscated is nice, that is not nice.
close(FILE);
Real programmers don't close files.
code
Real programmers don't write code.
Name:
Anonymous2006-10-21 13:29
Making things clear is not a bad strategy. You can do it in PERL too!
Name:
Anonymous2006-10-21 13:56
$_ is one of the worst features of Perl. I was going to say "the worst", but then I realized with @_, optional (), fucked up break/continue, shitty subs, default scoping, Hungarian notation, file handles, <>, regex straight into the language, $| and all these shitty variables, crappy OO, and mediocre standard functions, and more, it has a lot of competition.
ok thanks >>7 but like >>8 said the algorithm is non-optiomal,
but I need an optimal one.
Because if you have 700Mb and want to fit in 100,400 and 500 your algorithm would take the 100 and 500 files instead of the optimal 100 and 500, so thanks a lot for your effords but it's not quite what I wanted.
Now I have this 300pages long Book only on the napsack problem, dude I don't even understand half of the descibed algorithms but I think I'll get if I read it fully.
Because if you have 700Mb and want to fit in 100,400 and 500 your algorithm would take the 100 and 500 files instead of the optimal 100 and 500
Every redundant is a redundant redundant.
Since your files have equal value-to-size ratio, this is a variation of the bin packing problem, a derivative of the knapsack problem.
Quickest, easiest way of doing this without wasting too much space is to sort your candidate files by size in descending order. Iterate through them, slotting the file in if it fits, skipping it if it doesn't.
>>14 Quickest, easiest way of doing this without wasting too much space is to sort your candidate files by size in descending order. Iterate through them, slotting the file in if it fits, skipping it if it doesn't.
That's what I would do, without caring for better, yet much longer to develop and execute solutions, because the money I'd save is far less than the cost of my time to develop and run that.
Name:
Anonymous2006-10-22 11:17
You'll find that optimality isn't as important as maintaining consistent paths and locality of files.