verschiedene Dinge austauschen

damo

Hallo,
habe c.a. 3 Wochen darüber gearbeitet, kein Algorithmus gefunden.

Also, Es gibt 2 Listen,
eine ist so: z.B.9,7,7,3,3,2,2,2,1. (Liste_1)
die andere ist so: z.B.13,9,7,6,3,3. (Liste_2)

so jetzt sucht man, ob es in Liste_2 die Zahl gibt, die summe von die andere Zahlen ist, die Liste_1 hat. Wenn true ist, austauschen die Zahlen.

z.B. '6'(Liste_2) ist Summe von "2+2+2" ODER "3+3"(Liste_1)

habe nach subset sum Algorithmus gearbeitet, funktioniert bei Schritt 1, aber bei Austauschen, Wooo.....

vielen Dank vorher

Meep Meep

hola

sollten beim tauschen die werte der groesse nach wieder einsortiert werden ? oder an dem platz der zu tauschenden werte ?
wenn wie in deinem beispiel fuer '6' '3+3' oder '2+2+2' in frage kommt, welches ist da dann auszuwaehlen ?

Meep Meep

damo

sollten beim tauschen die werte der groesse nach wieder einsortiert werden ? oder an dem platz der zu tauschenden werte ?

Das spielt keine Rolle.

wenn wie in deinem beispiel fuer '6' '3+3' oder '2+2+2' in frage kommt, welches ist da dann auszuwaehlen ?

gute Frage! Wenn es in frage kommt, lieber '2+2+2' mit '6' tauschen, grundsätzliche Idee ist: lass die 'viele' und 'kleinere' Objekte mit '6' tauschen.

noch eine Bedingung ist vielleicht benutzbar: Liste_1, also die 'viele' und 'kleinere' ('2+2+2') Objekte enthält, die komplette Summe ist constant,z.B. 20, die Summe von der andere (Liste_2), kleiner als 20.

vielen Dank für Interesse

Meep Meep

re

wenn es eh egal ist, wo die werte einsortiert werden, dann nimmst aus jedem kontainer den / die werte raus und tust sie jeweils in den anderen kontainer einfuegen.

Meep Meep

damo

dann nimmst aus jedem kontainer den / die werte raus und tust sie jeweils in den anderen kontainer einfuegen.

???
die Werte und die Größe von Liste sollen beliebig sein.
z.B. Liste_1: 14 2 2 2 0
Alle Summe-Möglichkeit habe ich nach "subset-sum" gefunden: 20 18 16 14 6 4 2

wenn es in andere Liste '16' gibt, ok, aber habe ich die Positionen von "14, 2" in Liste_1 verloren. dann muss wieder in Liste_1 suchen, blöde, oder? so das ist mein Problem. Gibt es ein andere und effiziente Algorithmus?

Meep Meep

re

ok,nachmals ne verstaendnisfrage, weil ich grad auf der leitung steh:

wir haben 2 listen:

Liste1:
9,7,7,3,3,2,2,2,1

Liste2:
13,9,7,6,3,3

mit deinem algo untersuchst du nun wieviele werte aus Liste2 aus verschiedenen
werten der Liste1 bilden kannst. jeder wert aus Liste1 darf jedoch nur einmal
verwendet werden. wenn du das optimum erreicht hast und mit deiner suche fertig bist,
willst du die werte ausListe1(welche fuer einen wert in Liste2 verwendung finden)
in die Liste2 eintragen und den Wert aus Liste2 in Liste1 eintragen.

Liste2:             Liste1:
13      <-tauschen->        9 + 2 + 2
9       <-tauschen->        7 + 2
7       <-tauschen->        7
6       <-tauschen->        3 + 3
3       <-tauschen->        2 + 1
3                   find ich nix mehr

is das so richtig ?

Meep Meep

damo

die Werte und die Größe von Liste sollen beliebig sein.

13 <-tauschen-> 9 + 2 + 2

wie kann mann diese Ergebnisse praktisch finden? Wenn es tausende von Werte in Liste1 gibt? aus meinem Verständnis:

for (1~10000000) suche Summe von 1.wert + andere
for (2~10000000) suche Summe von 1.wert + 2.wert + andere
for (3~10000000) suche Summe von 1.wert + 2.wert + 3.wert + andere
........

oder benutzen wir Rekursion, auch ineffizient.

Meep Meep

woher bekommst du die werte ? in welchem wertebereich koennen die liegen ?
ist es das ziel moeglichst viele werte der Liste2 auszutauschen ? oder moeglichst viele aus der Liste1 rauszubekommen.

wo sind den unsere mathefreaks ?

Meep Meep