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?

array x sortieren

Backtracing über die Summenbildung

markieren

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

Hallo Oliver,

deine Aufgabenstellung kennen die Wirtschaftsinformatiker als Rucksack-Problem.

Grüße vom marabu

Zitat von freak4fun:

markieren

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:

markieren

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?

Zitat von TheAn00bis:

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

Ich darf das. Aber was ich gepostet hab ist ja nur ein Denkanstoß.

Zitat von backdraft:

Hat jemand einen anderen Lösungsansatz?

MfG
freak