AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Sortieren und kombinieren von Längen

Ein Thema von andone68 · begonnen am 2. Jun 2011 · letzter Beitrag vom 13. Jun 2011
Antwort Antwort
Seite 2 von 2     12   
andone68

Registriert seit: 22. Apr 2011
7 Beiträge
 
Delphi 6 Personal
 
#11

AW: Sortieren und kombinieren von Längen

  Alt 9. Jun 2011, 07:30
@jfheins:
Danke für den Tipp. Tatsächlich ist es das Untermengen-Problem. Wäre nie darauf gekommen dass das ein berümtes Problem der Informatik ist. Leider gibt es im i-net sehr wenig Infos darüber.
Bisherige interessante Links(abgesehen von deinen) sind:
http://www.clausbrod.de/cgi-bin/view...MacroSubsetSum
http://contest.spieleprogrammierer.de/06/

@Jens
Im i-net googeln ist eins, aber Nägel mit Köpfen machen ist was anderes.
Habe bisher leider noch nix (mit Delphi) machen können ausser deinen Code zu überfliegen. Verstanden hab ich den Schleifenaufbau noch nicht ganz aber das kommt bestimmt wenn ich am Wochenende mal wieder Zeit fürs programmieren habe. Wie die Objekte aussehen sollen ist mir auch noch schleierhaft, das kommt aber nur daher weil ich mir nie selber welche definiere. Vielleicht hast du da noch einen Tipp. Dann könnte ich schneller ein Testprogramm schreiben und dir ne Rückmeldung geben.

Gruß
andone68
  Mit Zitat antworten Zitat
Jens01

Registriert seit: 14. Apr 2009
673 Beiträge
 
#12

AW: Sortieren und kombinieren von Längen

  Alt 9. Jun 2011, 11:53
Morgen andone68,

ich habe mein altes Programm mal auseinandergenommen, was nicht so einfach (und zeitaufwendig!) war. Es war eben noch TP 7 und ich selbst habe damals noch nicht so sauber programmiert. Es lieferte aber dieselben Ergebnisse wie ein teures Profiprogramm.
Ich habe Sonntag und Montag versucht das auf Objektlisten umzustellen, was aber nicht so einfach war. Durchdenk Dir das Problem noch mal, dann guckn wir gemeinsam.

Gruss Jens

P.S.: Der Trick daran ist, dass vorab nach Große sortiert wird, die Kombinatorik wird dadurch um ein vielfaches vereinfacht. Es kommt aber trotzdem ein gutes Ergebnis raus.
  Mit Zitat antworten Zitat
andone68

Registriert seit: 22. Apr 2011
7 Beiträge
 
Delphi 6 Personal
 
#13

AW: Sortieren und kombinieren von Längen

  Alt 12. Jun 2011, 13:55
Konnte jetzt endlich weitermachen und hab als erstes mal die Beispielliste sortiert

Delphi-Quellcode:
unit KombiMain;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Label2: TLabel;
    procedure FormCreate(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

type TListe = record // Teilstück
    Lg : Integer; // Länge
    Bez : String; // Bezeichnung
  end;


var
  Form1: TForm1;

  // Listen der Teilstücke
  OListe: array of TListe; // Originalliste (also so wie eingegeben/unsortiert)
  SListe: array of TListe; // Sortierte Liste
  
implementation

{$R *.dfm}

Procedure ListeEinlesen;
begin
  SetLength(oListe, 1); oListe[ 0].Lg:=86; oListe[ 0].Bez:='1/1';
  SetLength(oListe, 2); oListe[ 1].Lg:=41; oListe[ 1].Bez:='2/1';
  SetLength(oListe, 3); oListe[ 2].Lg:=58; oListe[ 2].Bez:='2/2';
  SetLength(oListe, 4); oListe[ 3].Lg:=87; oListe[ 3].Bez:='2/3';
  SetLength(oListe, 5); oListe[ 4].Lg:=86; oListe[ 4].Bez:='2/4';
  SetLength(oListe, 6); oListe[ 5].Lg:=78; oListe[ 5].Bez:='2/5';
  SetLength(oListe, 7); oListe[ 6].Lg:=86; oListe[ 6].Bez:='2/6';
  SetLength(oListe, 8); oListe[ 7].Lg:=77; oListe[ 7].Bez:='2/7';
  SetLength(oListe, 9); oListe[ 8].Lg:=83; oListe[ 8].Bez:='2/8';
  SetLength(oListe,10); oListe[ 9].Lg:=90; oListe[ 9].Bez:='3/1';
  SetLength(oListe,11); oListe[10].Lg:=44; oListe[10].Bez:='3/2';
  SetLength(oListe,12); oListe[11].Lg:=57; oListe[11].Bez:='3/3';
  SetLength(oListe,13); oListe[12].Lg:=73; oListe[12].Bez:='3/4';
  SetLength(oListe,14); oListe[13].Lg:=72; oListe[13].Bez:='3/5';
  SetLength(oListe,15); oListe[14].Lg:=65; oListe[14].Bez:='3/6';
  SetLength(oListe,16); oListe[15].Lg:=65; oListe[15].Bez:='3/7';
  SetLength(oListe,17); oListe[16].Lg:=64; oListe[16].Bez:='3/8';
  SetLength(oListe,18); oListe[17].Lg:=60; oListe[17].Bez:='3/9';
  SetLength(oListe,19); oListe[18].Lg:=73; oListe[18].Bez:='3/10';
  SetLength(oListe,20); oListe[19].Lg:=72; oListe[19].Bez:='3/11';
end;

procedure SortiereListe;
var i,j,k : Integer;
   LgTemp : integer;
   BezTemp : string;
   N : Integer; // Anzahl Listeneinträge
begin

  n:=Length(oListe);
  SetLength(sListe,n);

  for i:=1 to n do begin // sliste:= oListe (kopieren)
    sListe[i-1].Lg := oListe[i-1].Lg;
    sListe[i-1].Bez := oListe[i-1].Bez;
  end;

  // BubbleSort
  For i:=0 to N-2 do begin
  
     k := i; // Position des größten Elementes initialisieren
     For j := i+1 to N-1 do // Nun wird das größte Elemente im Array [i..N-1]
       If sListe[k].Lg < sListe[j].Lg Then// gesucht und in k die Position gemerkt
         k := j; // '<' mit '>' vertauschen, wenn AUFsteigend sortiert wird.
                       // k enthält die Position des größten Elementes [i..N]

     If i <> k then Begin// Vertauschen

       LgTemp := sListe[i].lg;
       sliste[i].Lg := sliste[k].Lg;
       sliste[k].Lg := LgTemp;

       BezTemp := sListe[i].Bez;
       sliste[i].Bez := sliste[k].Bez;
       sliste[k].Bez := BezTemp;

     End;

   End;
   
end;


procedure TForm1.FormCreate(Sender: TObject);
Var s : string;
    i : Integer;
    n : Integer;
    t : String;
begin

  ListeEinlesen;

  SortiereListe; // sListe ist jetzt sortiert

  n:=Length(oListe);
  t:='';
  for i:=0 to n-1 do begin
    Str(oliste[i].Lg,s);
    t:=t+s+' - '+oListe[i].Bez+chr(10);
  end;
  Label1.Caption:=t;

  t:='';
  for i:=0 to n-1 do begin
    Str(sliste[i].Lg,s);
    t:=t+s+' - '+sListe[i].Bez+chr(10);
  end;
  Label2.Caption:=t;

end;

end.
Jetzt muss ich "nur noch" deinen Code testen
Wie er funktioniert hab ich zwar immer noch nicht ganz verstanden, werde mich aber dazu noch melden.
  Mit Zitat antworten Zitat
Jens01

Registriert seit: 14. Apr 2009
673 Beiträge
 
#14

AW: Sortieren und kombinieren von Längen

  Alt 12. Jun 2011, 23:29
TList oder TObjectList hat eine Sortiermethode Sort. Wie diese genau functioniert steht in einigen Forenbeiträgen drin. Welche Delphiversion benutzt Du?
http://www.delphipraxis.net/48466-tobjectlist.html

Geändert von Jens01 (12. Jun 2011 um 23:35 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#15

AW: Sortieren und kombinieren von Längen

  Alt 13. Jun 2011, 01:30
Welche Delphiversion benutzt Du?
Wenn man das eigene Profil entsprechend bestücken würde, dann wäre diese Frage überflüssig
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
andone68

Registriert seit: 22. Apr 2011
7 Beiträge
 
Delphi 6 Personal
 
#16

AW: Sortieren und kombinieren von Längen

  Alt 13. Jun 2011, 20:57
Benutze Delphi 6PE
Profil wird ausgeüllt, Danke für den Hinweis
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 2 von 2     12   


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine 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 aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 00:23 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz