php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Entwicklung > HTML, JavaScript, AJAX, jQuery, CSS, Bootstrap, LESS
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


HTML, JavaScript, AJAX, jQuery, CSS, Bootstrap, LESS Probleme mit HTML5, Bootstrap oder jQuery ?

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #1 (permalink)  
Alt 19-09-2003, 23:39
schindl
 Newbie
Links : Onlinestatus : schindl ist offline
Registriert seit: Sep 2003
Beiträge: 2
schindl ist zur Zeit noch ein unbeschriebenes Blatt
Standard [JavaScript] Matrix-Problem

Hallo,

vor einigen Tagen habe ich angefangen etwas Javascript zu lernen. Nun habe ich ein Problem bei dem ich nicht weiter komme:

- Es muss die Zahlenkombination errechnen werden, die unter folgenden Bedingungen die grösste Summe ergibt:

- Ich habe eine Matrix mit 20 Zeilen und 8 Spalten.

- Von jeder Zeile muss eine Zahl genommen werden (dürfen aber nicht mehr sein).

- Es dürfen maximal 5 Zahlen aus der selben Spalte genommen werden

Ich hoffe jemand kann mir weiterhelfen.
Mit Zitat antworten
  #2 (permalink)  
Alt 20-09-2003, 08:53
Titus
 PHP Master
Links : Onlinestatus : Titus ist offline
Registriert seit: Jan 2001
Ort: im Rodgau
Beiträge: 4.292
Titus ist zur Zeit noch ein unbeschriebenes Blatt
Standard

ähm ... whatisthematrix.com ... klingt eher als seist du auf der Suche nach einem Algorithmus.

ein Wert aus jeder der m Zeilen - max. k Werte aus einer Spalte
PHP-Code:
m=8n=20k=5;
matrix = new Array(
    
1,  2,  3,  4,  5,  6,  7,  8,
   
1112131415161718,
  ...
  
191,192,193,194,195,196,197,198,
  
201,202,203,204,205,206,207,208
); 
das einfachste wär natürlich brute force (brutale Gewalt) = für alle Kombinationen mit n Werten aus verschiedenen Zeilen - erst Vailiditäts-Check (max. k Werte je Spalte?), dann Summe berechnen:
PHP-Code:
ergebnisse = new Array();
zaehler = new Array();
zaehler.length m;
// kombi mit der ersten passenden Kombination initialisieren
// Ergebnis: kombi = (0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3)
kombi = new Array();
kombi.length n;
for(
zeile=0,wert=-1zeile<nzeile++)
{
  if (!(
zeile k)) wert++; // alle k Zeilen wert erhöhen
  
kombi[zeile] = wert;
}
maxkombi '-'maxsumme=0;
do
{
  
// maximal 5 Werte aus einer Spalte?
  // (= max. 5x den gleichen Buchstaben)
  // dabei gleich die Summe bilden
  
summe 0;
  for(
spalte=0spalte<mspalte++)
    
zaehler[spalte] = 0;
  for(
ok truezeile=0ok && zeile<nzeile++)
  {
    
spalte kombi[zeile];
    if (++
zaehler[spalte] > k)
      
ok false;
    else
      
summe += matrix[zeile*spalte];
  }

  
// ja: Summe mit bisherigem Maximum vergleichen
  
if (ok && summe>maxsumme)
  {
    
maxsumme summe;
    
maxkombi kombi.join(',');
  }

  
// Hochzählen
  
for(zeile=n-1zeile>=0zeile--)
  {
    
wert kombi[zeile]+1;
    if (
m==wertwert 0// Überlauf bei m
    
kombi[zeile] = wert;
    if (
wert) break; // kein Überlauf: Abbruch
  
}
} while(
zeile>=0// Abbruch bei Überlauf an erster Stelle
alert ('Kombination mit der höchsten Summe: '
  
maxkombi '; Summe=' maxsumme); 
Bei den Dimensionen deiner Matrix wären das etwa 20^8 = 25,6 Milliarden Durchläufe; und das ist wohl weniger akzeptabel. Selbst wenn dein Rechner zehn Millionen Durchläufe pro Sekunde schaffen sollte, braucht das Skript über 40 Minuten, um ein Ergebnis auszuspucken - und bis dahin hat dein Browser das Skript schon x-mal unterbrochen, um dich zu fragen ob es weiter ausgeführt werden soll.

Aber es gibt ein paar einfache Methoden, das etwas zu beschleunigen, und ein paar kompliziertere. Der flotteste Algorithmus, der mir auf die Schnelle einfällt ist dieser hier; eine Art quadriertes Backtracking:

Der erste Schritt für alle Beschleunigungsmaßnahmen bei diesem Problem: Man erstelle eine Index-Matrix, in der für jede Zeile die Indizes der Werte in absteigender Reihenfolge gespeichert werden.
ein Beispiel - 3x3-Matrix; es darf maximal ein Wert aus jeder Spalte kommen:
m=n=3; k=1;
matrix = new Array(
8, 15, 22,
3, 17, 9,
12, 3, 21
);
die Index-Matrix sieht so aus: (
2, 1, 0,
1, 2, 0,
2, 0, 1
);
Höchster Wert in der ersten Zeile ist die 22 an dritter Stelle = Position 2,
danach kommen 15 an Position 1 und die 8 ganz vorne (Position 0).
Die anderen Zeilen werden analog erstellt.

Dann fängt die Iteration an ... es werden jeweils für die ersten n Zeilen der Matrix die erste gefundene zulässige Index-Kombination samt der dazugehörigen Teilsumme gespeichert. Dadurch dass wir die Werte über die Index-Matrix absteigend sortiert haben, bekommen wir automatisch die beste.

bei obigem Beispiel ohne Vailidierung:
Zeile 0:
2 (22); weitere Kombinationen: 1 (15) - 0 (8)
Zeilen 0-1:
2, 1 (39);
weitere gültige Kombis:
2, 0 (22+3=25)
0, 1 (8+17=25)
1, 2 (15+9=24)
1, 0 (15+3=18)
0, 2 (8+9=17)

8, 15, 22,
3, 17, 9,
12, 3, 21

Nu kommt die Validierung dazu:[list=1][*]Die Kombination 2,1,2 (22+17+21 = 60) ist ungültig.[*]Also gehen wir zu vorigen Zeile zurück und suchen uns die nächst niedrigere gültige Kombination bis zu der Zeile: 2,0 (22+3=25)
Die Differenz zur höchsten Kombination 2,1(39) ist 14.[*]Bevor die jetzt verwurstet wird, schauen wir erst einmal nach, ob wir nicht einen Wert in der dritten Zeile finden, bei dem die Differenz geringer (oder gleich) ist; alles was >=21-14 ist passt also.
Die nächst niedrigere Zahl in der Zeile steht (wie uns die Index-Matrix sagt) an Position 0, es ist die 12. Das ist >=7[*]also schauen wir mal ob (2,1,1) gültig ist ... zwei Werte aus einer Spalte, also nicht.[*]nächste gültige zweizeilige Kombi + höchste aus Zeile 2: 2,0,2 (22+3+21 = 46) - passt aber auch nicht[*]nächste gültige zweizeilige Kombi ist die 0,1(8+17=25);
die Differenz zur vorigen Kombi ist 0. Also passt uns entweder die höchste aus der dritten Zeile oder alle gleichwerigen (die es nicht gibt)
0,1,2 passt aber schon; Wert: 8+17+21 = 46.[*]Wir haben eine Zahl aus der letzten Zeile hinzugefügt, damit ist die gültige Kombination mit der höchsten Summe gefunden.[/list=1]

Übrigens findet der brute-force-Algorithmus bei diesem Beispiel die gleiche Kombination, was aber nicht unbedingt sein muss.
Hier ist das etwa nicht der Fall:
matrix = new Array(
1,2,3,
1,2,3,
1,2,3
);
m=n=3; k=1;

brute force findet 0,1,2 mit Summe 6;
der andere Algorithmus wirft 2,1,0 mit der gleichen Summe aus.

---------------------------------------------------------------------------------

Zugegeben, der Algorithmus ist nicht ganz einfach zu implementieren; aber wenn du erst ein paar Monate JavaScript geübt hast und dann ein paar Tage Gehirnschmalz reinsteckst, kannst du hier ja mal das Ergebnis präsentieren.

Für den Anfang bau dir erstmal ein Skript, das die Index-Matrix erstellt.

Im bruteforce-Skript habe ich auch noch ein paar Möglichkeiten zur Beschleunigung gelassen; die wirst du allerdings erst mit viel Übung oder durch ausgiebiges Nachdenken über die Möglichkeiten der Sprache entdecken. (Die gleichen Möglichkeiten bieten sich aufgrund der Ähnlichkeit der Sprachen auch in C und Konsorten sowie PHP und natürlich Java.)

Auf jeden Fall empfehle ich Dir die ausgiebige Lektüre des JavaScript-Bereiches im selfHTML; da steht so ziemlich alles, was man über JavaScript wissen muss.
Ist auch prima als Nachschlagewerk geeignet; aber ich würd´s mir runterladen, die neue Werbeschaltung ist ein wenig lästig.
__________________
mein Sport: mein Frühstück: meine Arbeit:

Sämtliche Code-Schnipsel sind im Allgemeinen nicht getestet und werden ohne Gewähr auf Fehlerfreiheit und Korrektheit gepostet.

Geändert von Titus (20-09-2003 um 12:09 Uhr)
Mit Zitat antworten
  #3 (permalink)  
Alt 20-09-2003, 12:08
Titus
 PHP Master
Links : Onlinestatus : Titus ist offline
Registriert seit: Jan 2001
Ort: im Rodgau
Beiträge: 4.292
Titus ist zur Zeit noch ein unbeschriebenes Blatt
Exclamation

Ich hab mich bei Punkt 4. geirrt; natürlich muss hier die Kombi 2,1,0 überprüft werden (in 3 bin ich noch richtig mit der 0). Das ist eine gültige Kombination und liefert die Summe 51.

Das kommt davon wenn man sich so früh morgens an den Rechner setzt.
Mit Zitat antworten
  #4 (permalink)  
Alt 21-09-2003, 22:45
schindl
 Newbie
Links : Onlinestatus : schindl ist offline
Registriert seit: Sep 2003
Beiträge: 2
schindl ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Danke für deine ausführliche Antwort. Ich werde gleich mal versuchen deine Ratschläge umzusetzen, obwohl dass noch etwas tieferes Programmierverständnis erfordern wird, als ich im Moment habe.

Ich glaube du hast dich in noch einem Punkt geirrt, denn meiner Meinung nach sind es 8^20 Möglichkeiten, was Jahre dauern würde.
Mit Zitat antworten
  #5 (permalink)  
Alt 22-09-2003, 09:55
Titus
 PHP Master
Links : Onlinestatus : Titus ist offline
Registriert seit: Jan 2001
Ort: im Rodgau
Beiträge: 4.292
Titus ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Hast recht, 8^20 = 2^23 = 1 152 921 504 606 846 976
bei 10 Mio cycles/sec ca. 3656 Jahre

Aber kannst ja mal mit nem einfachen Backtracking anfangen. Das such zwar nach kürzesten Wegen; aber mit einer einfachen Umformung der Matrix ist das schnell erledigt:

M2[x,y] = 1+max(M1)-M1[x,y]

Und die Laufzeit bei deinen Dimensionen ist halbwegs akzeptabel,
aolange du nur eine Rekursion startest, wenn die neue Kombination gültig ist.

Sprich:
1. zur aktuellen Kombi suchst du die Spaltennummern, die noch nicht ausgereizt sind, bevor du diese an die Kombi anhängst und damit in die Rekursion gehst.
2. Noch mehr Zeit sparst du, wenn du die bisherige Summe als zweiten Parameter mitschickst.
__________________
mein Sport: mein Frühstück: meine Arbeit:

Sämtliche Code-Schnipsel sind im Allgemeinen nicht getestet und werden ohne Gewähr auf Fehlerfreiheit und Korrektheit gepostet.
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

Die RIGID-FLEX-Technologie
Die RIGID-FLEX-TechnologieDie sogenannte "Flexible Elektronik" , oftmals auch als "Flexible Schaltungen" bezeichnet, ist eine zeitgemäße Technologie zum Montieren von elektronischen Schaltungen.

06.12.2018 | Berni

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni


 

Aktuelle PHP Scripte

Newsmanager

Der Newsmanager ist ein Newssystem und Newsletter in einem. Mit WYSIWYG Editor und E-Mail import aus einer bestehenden MySql Datenbank sowie dynamische Kategorien / Themen Filter.

11.09.2019 Stephan_1972 | Kategorie: PHP/ News
Modelmanager

Der Modelmanager ist ein Webtool für Fotografen, kann als komplette Homepage oder als Webtool installiert werden.

11.09.2019 Stephan_1972 | Kategorie: PHP/ Webservice
ContentLion - Open Source CMS ansehen ContentLion - Open Source CMS

ContentLion ist ein in PHP geschriebenes CMS, bei dem man Seiten, Einstellungen usw. in Ordnern lagern kann

22.08.2019 stevieswebsite2 | Kategorie: PHP/ CMS
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 21:19 Uhr.