Bruteforce, ich kriegs nicht hin

  • Themenstarter Themenstarter IKEAFREAX
  • Beginndatum Beginndatum
I

IKEAFREAX

Ich hab über suchen schon nen Thread gefunden, hat mir leider nicht weitergeholfen.

Ich habe zwei Array, name und size.
In name sind die Dateinamen drin, in size die Dateigrößen.

Auf ne DVDR krieg ich 4,5 GB, ich will herausfinden, welche kombination die 4,5 GB am besten ausnutzt.
Hat wer ne Idee?
 
a: 12
b: 43
c: 6
d: 34

benötigt: 20

lösung: a + b

brutforce:
a + b = 55
somit entfallen alle summen in denen a und b vorkommen

so, dass nun mit allen kombinationen (sollte mit ner schleife kein problem sein)
diese ergebnisse in ein array speicher, und die einzelnen werte dann mit dem gewünschten zielwert vergleichern (mit < > =)


weiter bin ich nonet gekommen...

werd gleich noch n bisschen rumprobieren...
 
Zuletzt bearbeitet von einem Moderator:
wie wäre es, wenn du es so machst, dass du ersteinmal probierst, die zwei größten dateien zusammenzuzählen um möglichst nah an deine 4.5 GB heranzukommen. danach wirfst du die kleinste Datei raus und ersetzt diese durch zwei jeweils kleinere, bzw zusammen größere, immer abhängig von der datenmenge, welche überschüssig oder eben noch frei ist.

diesen vorgang machst du immer weiter und näherst dich damit stark den 4.5 GB an.
Die Mathematiker nennen das IMHO Intervallschachtelung, jedenfalls kommt es dem nahe.

das ganze ist natürlich ein problem, wenn du nur große dateien hast und nciht auch mal "lückefüller".

eine idee mehr zu bedenken.. ;-)
 
@brainstor: An die Möglichkeit hab ich auch schon gedacht, allerdings ist diese, wie du schon gesagt hast, u.U. ungenau.


Ich hab hier mal was gemacht (habs in JavaScript gemacht, weil ich momentan keine PHP Umgebung da hab):

PHP: 
<html>
<head>

<script type="text/javascript">

zahlen = new Array();

zahlen.push("3");
zahlen.push("2");
zahlen.push("4");
zahlen.push("11");
zahlen.push("8");
zahlen.push("7");

maxworth = 15;
erg = new Array();
stillhad = new Array();

for (i=0; i<zahlen.length; i++) {
    erg_tmp = "";
    stillhad[i] = new Array();
    stillhad[i].push(i);
    zahl = zahlen[i];
    atpos = 0;
    abbr = 0;

    ////////////////////////
    //zaehl = 0;
    ////////////////////////

    while (abbr == 0) {
        if (partOf(atpos, stillhad[i]) == false) {
            zahl += zahlen[atpos];
            erg_tmp += "|"+atpos;
            stillhad[i].push(atpos);
        }

        atpos++;

        document.write(erg_tmp + "<br>");
        document.write(atpos + "<br>");
        document.write(zahl + "<br><br>");
        //document.write(stillhad[i] + "<br>");

        if (zahl < maxworth) {
            if (partOf(erg_tmp, erg) == false) {
                erg[zahl] = erg_tmp;
                erg_tmp = "";
            }
        }

        if (zahl == maxworth) {
            erg[maxworth] = erg_tmp;
            abbr = 1;
        }

        if (atpos == (zahlen.length + 1))
            atpos = 0;

        if (zahl > maxworth)
            abbr = 1;

        //////////////
        //zaehl++;

        //if (zaehl > 100)
        //    abbr = 1;
        ////////////
        /////////////////
    }
}

function partOf(strng, arr) {
    for (z=0; z<arr.length; z++) {
        if (arr[z] == strng)
            return z;
    }

    return false;
}


document.write(erg);
</script>

</head>
<body>

</body>
</html>

Funktioniert allerdings nicht so, iwe ich mir das vorstelle ;).
Vielleicht findet ja jemand den Fehler, ich halt mich jedenfalls auch ran...
 
Bruteforce ist ist ein (zugegeben sehr unelegante) Methode, um irgend eine Lösung heraus zufinden. Dabei wird jedem Kombination, bzw. Möglichkeit ausbrobiert. UNd das solange bis eine Passt.


Diese Methode wird auch oft von Hackern benutzt, die versuchen, in einen Account, oder sonst was, reinzukommen. Das machen sie, indem sie alle Wörter die es gib (bis zu einer bestimmten Länge) generieren lassen, und benutzten dies dann als Passwort. (<- Das habt ihr niocht von mir ;) )
 
Hm, also Bruteforce macht hier nur bei relativ wenigen Dateien (< 20) Sinn. Trotzdem hier mal meine Idee:

PHP: 
<?
$sizes = array(/* ... */);
$names = array(/* ... */);

$dvdsize = 4500000; // Näherungswert ;)

$max = pow(2, count($sizes));
$bestsum = 0;

for ($mask=0; $mask<$max; $mask++) {
	$sum = 0; $files = array();
	for ($i=0; $i<count($sizes); $i++) {
		if ((1<<$i) & $mask) {
			$sum += $sizes[$i];
			$files[] = $i;
		}
		if ($sum >= $dvdsize) break;
	}
	if ($sum <= $dvdsize && $sum > $bestsum) {
		$bestsum = $sum;
		$bestfiles = $files;
	}
	if ($bestsum == $dvdsize) {
		break;
	}
}

foreach ($bestfiles as $i) {
	echo $names[$i]." (".($sizes[$i]).")<br>\n";
}
echo "Summe: ".$bestsum;
?>
Die Anzahl der Schleifendurchläufe wächst natürlich exponential mit der Anzahl der Dateien, wenn man davon ausgeht, dass keine ideale Kombination gefunden wird... mal sehen ob ich einen etwas optimierteren Code zusammenschnipseln kann.
 
*gib reima einen dicken schmatz*

(edit)
kannst du mir mal bitte kurz die funktion von
PHP: 
((1<<$i)_&_$mask)
erklären?
 
Mein Algorithmus baut auf der binären Natur dieses Problems auf. Bei einer möglichen Lösung ist jede Datei entweder enthalten (1) oder nicht (0). Um jetzt alle Möglichkeiten durchzuprobieren, lasse ich meine Laufvariable ($mask) von 0 bis 2^n durchlaufen, wobei n = Anzahl der Dateien. Für jeden Durchlauf prüfe ich nun in einer weiteren Schleife, ob das jeweilige Bit für die Datei $i gesetzt ist. Und das mache ich mit ((1<<$i) & $mask), was soviel heißt wie: Nimm die Zahl 1 und verschiebe sie binär um $i nach links (bei $i=5 würde also 100000b rauskommen). Der binäre Operator '&' arbeitet nun so, dass im Ergebnis genau die Bits gesetzt sind, die in den beiden Operanden gesetzt sind. Bei meinem ersten Operanden (1<<$i) ist ja sowieso nur ein Bit gesetzt, also kann man die anderen gleich schon mal wegfallen lassen. Ist nun dieses Bit auch in $mask gesetzt, ergibt '&' ein Ergebnis != 0 (= true). Andernfalls kommt natürlich 0 (= false) raus.

Somit sollten eigentlich alle Klarheiten beseitigt sein ;)
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück