Array berechnen

[backdraft]

Hallo zusammen,

ich habe folgende Aufgabenstellung:

Ich habe einen Array mit x-Zeilen die Zahlen enthalten
Auf der anderen Seite habe ich eine Zahl y.

Jetzt möchte ich wissen, welche der Array Positionen in Summe die Zahl y ergeben.

Ich habe es mit Binärschaltung versucht. Das ganze geht gut, solange ich ein paar Positionen drin habe.
Sobald ich aber schon 100 Zeilen im Array habe, läuft er sich tot.

Hat jemand einen anderen Lösungsansatz?

[Kroko1999]

array x sortieren

Backtracing über die Summenbildung

[freak4fun]

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  i, j, y: Integer;
begin
  y := StrToInt(Edit1.Text);
  for i := Low(MyArray) to High(MyArray) do
    for j := Low(MyArray) to High(MyArray) do
      if MyArray[i] + MyArray[j] = y then
        ListBox1.Items.Add(Format('I: %d J: %d', [i, j]));
end;

MfG
freak

[marabu]

Hallo Oliver,

deine Aufgabenstellung kennen die Wirtschaftsinformatiker als Rucksack-Problem.

Grüße vom marabu

[TheAn00bis]

Zitat:

Zitat von freak4fun

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  i, j, y: Integer;
begin
  y := StrToInt(Edit1.Text);
  for i := Low(MyArray) to High(MyArray) do
    for j := Low(MyArray) to High(MyArray) do
      if MyArray[i] + MyArray[j] = y then
        ListBox1.Items.Add(Format('I: %d J: %d', [i, j]));
end;

MfG
freak

Man darf doch nicht eines mit sich selbst addieren, oder?
Also:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject); 
var 
  i, j, y: Integer; 
begin 
  y := StrToInt(Edit1.Text); 
  for i := Low(MyArray) to High(MyArray) do 
    for j := Low(MyArray) to High(MyArray) do 
      if (MyArray[i] + MyArray[j] = y) and (i<>j) then 
        ListBox1.Items.Add(Format('I: %d J: %d', [i, j])); 
end;

Oder sehe ich da was falsch?

[freak4fun]

Zitat:

Zitat von TheAn00bis

Man darf doch nicht eines mit sich selbst addieren, oder?

Ich darf das. :mrgreen: Aber was ich gepostet hab ist ja nur ein Denkanstoß. ;)

Zitat:

Zitat von backdraft

Hat jemand einen anderen Lösungsansatz?

MfG
freak