Forum: Gesperrte Threads Dringend: Welche Zahlen Z1.Zn muß ich addieren, um auf Betrag B zu kommen.


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Peter (Gast)


Bewertung
-13 lesenswert
nicht lesenswert
Nehmen wir an, ich habe Zahlen

1,2
4,5
3,4
10,2

und ich möchte wissen, welche Zahlen ich addieren muß, um auf Betrag B 
zu kommen. Also etwa(Anstatt 1,2 4,5 etc, verwende ich jetzt Z1, Z2, 
...)

F1...FN sind entweder 1 oder 0 und sollen bestimmt werden.

Z1*F1+Z2*F2+...=B

Will ich etwa 4,6 für B, sieht es so aus:

(1,2*1)+(4,5*0)+(3,4*1)+(10,2*0) = 4,6

Ich verwende c#.

Also nochmal kurz, das Programm soll beantworten:

Welche Zahlen Z1...Zn muß ich addieren, um auf Betrag B zu kommen.

Bitte einfach mal einen Code veröffentlichen, ich habe einfach keine 
Zeit groß rumzufummeln - oder einen Link zu einem Onlineservice, bei dem 
ich das machen kann. Oder in einer Tabellenkalkulation, egal, hauptsache 
schnell und richtig.

Danke

: Verschoben durch Moderator
von Olmau (Gast)


Bewertung
5 lesenswert
nicht lesenswert
Wieso dringend? Finde ich ziemlich frech.

von Peter (Gast)


Bewertung
-6 lesenswert
nicht lesenswert
Ist dringend, bitte schnell antworten.

von radiostar (Gast)


Bewertung
4 lesenswert
nicht lesenswert
Mach Deine Hausaufgaben gefälligst selber und belästige nicht Leute 
damit, die Du nichtmal kennst.

von Peter (Gast)


Bewertung
-7 lesenswert
nicht lesenswert
Ist dringend, bitte nicht ablenken und schnell antworten.

von Christian M. (Gast)


Bewertung
3 lesenswert
nicht lesenswert
Bist Du mitten in einer Prüfung?

Gruss Chregu

von Joe S. (joesch)


Bewertung
6 lesenswert
nicht lesenswert
Ne, wahrscheinlich auf der Toilette. Die Prüfung ist woanders. :)

von Peter (Gast)


Bewertung
-6 lesenswert
nicht lesenswert
Bitte nicht ablenken sondern antworten.

von Dirk B. (dirkb2)


Bewertung
4 lesenswert
nicht lesenswert
Z1, Z3 und Z8, wenn B 42 ist

Wenn aber Z14=Z8 ist, kannst du auch die nehmen.

von Achim H. (anymouse)


Bewertung
0 lesenswert
nicht lesenswert
Rucksack-Problem ?

Alternativ: Alle Möglichkeiten probieren, und  bei der ersten passenden 
aussteigen.

Randproblem: Ist sichergestellt, dass überhaupt eine Lösung existiert?

von Peter (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
Bitte einfach mal einen Code veröffentlichen, ich habe einfach keine
Zeit groß rumzufummeln - oder einen Link zu einem Onlineservice, bei dem
ich das machen kann. Oder in einer Tabellenkalkulation, egal, hauptsache
schnell und richtig.

von Verweigerer (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Nein!

von Berufsberater (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Wie ich das jetzt so sehe gibt es bei deinem Problem 16 verschiedene 
Lösungen. Die hättest du schneller per Kopf ausgerechnet als hier 
überhaupt die erste Frage zu stellen.

von Dirk B. (dirkb2)


Bewertung
1 lesenswert
nicht lesenswert
Verweigerer schrieb:
> Nein!

Doch!

von Helmut L. (helmi1)


Bewertung
2 lesenswert
nicht lesenswert
Der will doch Cheffe werden und uebt schon mal das deligieren von 
Aufgaben.

von aGast (Gast)


Bewertung
2 lesenswert
nicht lesenswert
Ich glaub der TO ist raus, die Zeit auf der Toilette ist abgelaufen.
Tja blöd gelaufen, das wird dann wohl keinen gute Note werden.

von Peter (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
Wenn ich von
00000...
bis zu
11111...

binär durchzählen will, also nur mit 1 und 0, wie mache ich das - 
vorausgesetzt, die 1er und 0er-Ketten sind gleich lang und zwar n 
Stellen.

von oder... (Gast)


Bewertung
3 lesenswert
nicht lesenswert
Helmut L. schrieb:
> Der will doch Cheffe werden [...]


Die erste Hürde dazu ist genommen:
wie man sich unbeliebt macht, hat er schon drauf

von Klaus Dieter (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Du stellst irgendwie wirre Fragen.

von oder... (Gast)


Bewertung
-3 lesenswert
nicht lesenswert
Bitte nicht ablenken sondern antworten.

von vorticon (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Zaehle von i = 0 bis 2^n-1 durch
und teste in der Schleife die Bits mit (i & (1<<k)).

Fuer grosse n laesst sich das Problem als Optimierungsproblem loesen.

in Matlab:
x=[1.2 4.5 3.4 10.2];
n=numel(x);
F=intlinprog(ones(n,1),1:n,[],[],x,4.6,zeros(1,n),ones(1,n))

Ansonsten, mehr als dumme Antworten wirst du mit der Frage in diesem 
Forum selten bekommen...

von Olmau (Gast)


Bewertung
0 lesenswert
nicht lesenswert
vorticon schrieb:
> Zaehle von i = 0 bis 2^n-1 durch
> und teste in der Schleife die Bits mit (i & (1<<k)).
>
> Fuer grosse n laesst sich das Problem als Optimierungsproblem loesen.
>
> in Matlab:
> x=[1.2 4.5 3.4 10.2];
> n=numel(x);
> F=intlinprog(ones(n,1),1:n,[],[],x,4.6,zeros(1,n),ones(1,n))
>
> Ansonsten, mehr als dumme Antworten wirst du mit der Frage in diesem
> Forum selten bekommen...

Danke - für die bisher dümmste Antwort.

von vorticon (Gast)


Bewertung
2 lesenswert
nicht lesenswert
Olmau schrieb:
> Danke - für die bisher dümmste Antwort.

Mensch spar dir die Muehe, anderen Menschen auf die Nerven zu gehen. Was 
soll der Kindergarten?

von Berufsberater (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Peter schrieb:
> Wenn ich von
> 00000...
> bis zu
> 11111...

z.B. einfach i++;

eine Variable ist im System immer eine Folge von 0 und 1. DEZ, HEX, OCT 
u.s.w. sind einfach nur andere mögliche Formen den Inhalt für einen 
Benutzer darzustellen.

von Markus W. (dl8mby)


Bewertung
0 lesenswert
nicht lesenswert
Mein Vorschlag zur Sache

Annahme alle Zahlen sind unique.

1) Zahlen Aufsteigend sortieren.
2) Alle Faktoren zu 0 für alle Zahlen > B
3) Größte Zahl aus der verbleibenden Liste
   nehmen, die < B und deren Faktor auf 1 setzen.
4) B um diese Zahl reduzieren zu B' und rekursiv
   bei 2) wieder anfangen, bis B'==0 sonst keine Lösung.

Hoffe soweit das Problem begriffen und gelöst zu haben.

Gruß
Markus

von Peter (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Berufsberater schrieb:
> Peter schrieb:
>> Wenn ich von
>> 00000...
>> bis zu
>> 11111...
>
> z.B. einfach i++;
>
> eine Variable ist im System immer eine Folge von 0 und 1. DEZ, HEX, OCT
> u.s.w. sind einfach nur andere mögliche Formen den Inhalt für einen
> Benutzer darzustellen.

Bei mehr als 20 Stellen paßt es nicht einmal mehr in Int64.

von vorticon (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Markus W. schrieb:
> 1) Zahlen Aufsteigend sortieren.
> 2) Alle Faktoren zu 0 für alle Zahlen > B
> 3) Größte Zahl aus der verbleibenden Liste
>    nehmen, die < B und deren Faktor auf 1 setzen.
> 4) B um diese Zahl reduzieren zu B' und rekursiv
>    bei 2) wieder anfangen, bis B'==0 sonst keine Lösung.
>
> Hoffe soweit das Problem begriffen und gelöst zu haben.

Damit loest du das Problem im Allgemeinen nicht. Denn es ist nicht 
gesagt, dass der Koeffizient der groessten Zahl <=B gleich eins sein 
muss. Du musst entweder alle 2^n Moeglichkeiten durchprobieren, oder 
effizient als Optimierungsproblem loesen.

von Peter (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
Können wir uns bitte auf das Hauptproblem beschränken? Das ist

Welche Zahlen Z1...Zn muß ich addieren, um auf Betrag B zu kommen.

Die Sache mit

"Wenn ich von
00000...
bis zu
11111...

binär durchzählen will, also nur mit 1 und 0, wie mache ich das -
vorausgesetzt, die 1er und 0er-Ketten sind gleich lang und zwar n
Stellen."

ist ein Nebenschauplatz um F1...Fn zu ermitteln. Wenn es anders geht, 
bitte beim Hauptproblem bleiben. Das ist

Welche Zahlen Z1...Zn muß ich addieren, um auf Betrag B zu kommen.

von Berufsberater (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Peter schrieb:
> Bei mehr als 20 Stellen paßt es nicht einmal mehr in Int64.

Wo ist da das Problem?
Einfach überprüfen ob es zum Überlauf kommt und dann eine weiter 
Variable z.B. i2 inkrementieren. Da hast du schon mal die doppelte Bit 
Anzahl.
Reicht das immer noch nicht lässt sich das Spiel bis zum Maximalen RAM 
beliebig ausdehnen.

von vorticon (Gast)


Bewertung
2 lesenswert
nicht lesenswert
Die Frage wurde doch bereits beantwortet. Die einfache, ineffiziente 
Loesung ist, alle Moeglichkeiten durchzuprobieren. Die effiziente 
Loesung siehe oben.

von Peter (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Make the first cell (Cell 0) hold a value of 48
>++++ ++++
[
<++++ ++
>-
]

#Get inputs and minus 48 from each to get Decimal

,>,
<<
[
>-
>-
<<-
]

#Adds the contents of Cells 1 and 2


>
[
>+
<-
]

#Moves answer to Cell 0
>
[
<+
>-
]
<
[
<+
>-
 ]

#Converts answer to ASCII
>++++ ++++
[
<++++ ++
>-
]
<

[
<+
>-
]
<
#Print answer
.

von Markus W. (dl8mby)


Bewertung
0 lesenswert
nicht lesenswert
Neuer Versuch ;-)

Alle möglichen Summen der Zahlen Reihe bilden und die
Distanz/Differenz zu B bestimmen. Falls dieser Wert = Null
Problem gelöst, ansonsten nicht lösbar.
Ist halt mehr Brut Force Ansatz.

Beim ersten Ansatz habe ich wohl übersehen, dass auch mehrere
kleine Zahlen in der Summe B ergeben können und dazu nicht
die Größte Zahl, die noch in B hineinpasst erforderlich ist.
Somit hast Du recht vorticon.

Markus

von Markus W. (dl8mby)


Bewertung
0 lesenswert
nicht lesenswert
Kann jemand von Euch sagen, ob es das intlinprog
wie im Link beschrieben
https://de.mathworks.com/help/optim/ug/intlinprog.html
auch für Octave gibt?

Markus

von vorticon (Gast)


Bewertung
0 lesenswert
nicht lesenswert
In Octave gibt es die Funktion glpk
https://www.gnu.org/software/octave/doc/v4.0.0/Linear-Programming.html

Mit folgendem Aufruf geht es:
glpk(ones(1,4),[1.2 4.4 5.7 3.1],5.6,zeros(1,4),ones(1,4),'S','IIII')

Gruss vorticon

von Markus W. (dl8mby)


Bewertung
0 lesenswert
nicht lesenswert
Danke für die Info!


Bekomme trotzdem noch eine Fehlermeldung,
>> glpk(ones(1,4),[1.2 4.4 5.7 3.1],5.6,zeros(1,4),ones(1,4),'S','IIII')
error: glpk: not supported on this system
error: called from
    glpk at line 609 column 27

obwohl ich das glpk Paket installiert habe.
The following 2 NEW packages are going to be installed:
  glpk glpk-doc
...
(1/2) Installing: glpk-doc-4.55-4.4.noarch 
.........................[done]
(2/2) Installing: glpk-4.55-4.4.x86_64 
.............................[done]

Hast Du möglicherweise eine Idee?

Danke!

Markus

von brainfuck (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Der Peter hat es auf den Punkt gebracht.
Danke Peter

von Markus W. (dl8mby)


Bewertung
0 lesenswert
nicht lesenswert
Hallo vorticon,

>> glpk help funktioniert
error: Invalid call to glpk.  Correct usage is:

 -- Function File: [XOPT, FMIN, ERRNUM, EXTRA] = glpk (C, A, B, LB, UB,
          CTYPE, VARTYPE, SENSE, PARAM)

Additional help for built-in functions and operators is
available in the online version of the manual.  Use the command
'doc <topic>' to search the manual index.

Help and information about Octave is also available on the WWW
at http://www.octave.org and via the help@octave.org
mailing list.

und

>> doc glpk liefert ebenfalls eine Ausgabe.

25.1 Linear Programming
=======================

Octave can solve Linear Programming problems using the ‘glpk’ function.
That is, Octave can solve

     min C'*x

   subject to the linear constraints A*x = b where x ≥ 0.

The ‘glpk’ function also supports variations of this problem.
....

Möglicherweise hat sich die Aufrufnotation geändert.

Gruß
Markus

von vorticon (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hallo Markus,
sieht so aus, dass glpk auf deinem Rechner nicht unterstuetzt wird. 
Genaueres kann ich nicht sagen. Unter Linux laeuft es bei mir. Wir nicht 
am Aufruf liegen, denke ich. Vielleicht mal andere Version probieren. 
Kenne mich mit Octave aber nicht so gut aus. Octave ist cool, aber 
Matlab kann eigentlich fast alles besser - daher nutze ich nur Matlab...

vorticon

von Tim T. (tim_taylor) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Aus dem Rückenmark:
1
int main(void) {
2
 double auswahl[] = {1.2, 4.5, 3.4, 10.2};
3
 double B = 4.6;
4
 double temp;
5
6
 int zahlen = (sizeof(auswahl)/sizeof(double));
7
 int i,j;
8
 
9
 for (i=0; i<2<<(zahlen-1); i++) {
10
  temp = 0;
11
  for (j=0; j<zahlen; j++) temp+=auswahl[j]*((i>>j) & 1);
12
  if (temp == B) {
13
   for (j=0; j<zahlen; j++) printf("(%2.1f*%d)+", auswahl[j], ((i>>j) & 1));  
14
   printf("\b = %2.1f\n", B);
15
  }
16
 }
17
  
18
 return 0;
19
}

: Bearbeitet durch User
von Pete K. (pete77)


Bewertung
0 lesenswert
nicht lesenswert
Dann ist die Hausaufgabe ja gemacht und Peter kann spielen gehen.

von Tim T. (tim_taylor) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Nö, den Rest des Abends kann er es ja noch in c# umschreiben...

von Markus W. (dl8mby)


Bewertung
0 lesenswert
nicht lesenswert
Und der zugehörige Output

>./optimize
(1.2*1)+(4.5*0)+(3.4*1)+(10.2*0) = 4.600000

Markus

von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
Da das Problem so dringend war (warum auch immer) und es mittlerweile
Abend ist, ist dessen Lösung für Peter wahrscheinlich nicht mehr von
Interesse. Falls doch:

Die Wahl eines geeigneten Algorithmus (davon gibt es eine ganze Reihe)
hängt von ein paar Eigenschaften der Zahlenmenge ab:

1. Um wieviele Zahlen geht es typischerweise?

2. Ist der Wertebereich der Zahlen einseitig oder beidseitig beschränkt?
   Sind sie also bspw. immer positiv, oder liegen sie immer zwischen 1
   und 20?

3. Sind die Zahlenwerte diskret?
   Haben sie also bspw. maximal eine Nachkommastelle?

4. Gibt es irgendwelche Einschränkungen bzgl. der Summe B?

5. Oder geht es um ein ganz konkretes Problem mit fest vorgegebenen
   Zahlenwerten?
   Dann lässt sich vielleicht ein System darin entdecken, das die
   Lösung vereinfacht.

Unterliegend die Zahlenwerte und die Summe B keinen Einschränkungen, und
ist ihre Anzahl größer als ca. 100, ist das Problem in akzeptabler Zeit
nicht lösbar.

Hier ist noch eine Haskell-Variante der Primitivlösung, die der Reihe
nach die Teilsummen abklappert, bis eine Lösung gefunden wird:

1
find ((==b) . sum) (subsequences z)

z ist dabei die Liste der Zahlen (sollte nicht zu groß sein) und b
die gewünschte Summe. Der Code ist selbst für einen Nicht-Haskellianer
fast selbsterklärend:

Finde (find) in den Teillisten (subsequences) von z eine, deren
Summe (sum) gleich b (==b) ist. Möchte man nicht nur eine, sondern
alle Lösungen, ersetzt man einfach find durch filter.

Ja, so einfach kann Programmieren sein :)

von Mike B. (mike_b97) Benutzerseite


Bewertung
1 lesenswert
nicht lesenswert
Peter schrieb:
> Make the first cell (Cell 0) hold a value of 48
>>++++ ++++
> [
> <++++ ++
>>-
> ]

...

Ist das Brainfuck?

von MikeH (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Das ganze Problem lässt sich auf das Rucksackproblem zurückführen, wobei 
B die Tragfähigkeit des Rucksacks, Z1...Zn die "Gewichte" und F1...F1 
mitnehmen/liegenlassen bedeutet.

Da das Problem NP vollständig ist, dauert es im schlimmsten Fall sehr 
lange eine Lösung zu finden (exponentiell). Ein im Mittel 
erfolgversprechender Ansatz ist die Lösung mit dem  Backtracking 
Algorithmus.

von MikeH (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ergänzung: Genauer gesagt handelt es sich um das Teilsummenproblem 
https://de.wikipedia.org/wiki/Teilsummenproblem

von Walter S. (avatar)


Bewertung
0 lesenswert
nicht lesenswert
Tim T. schrieb:
> if (temp == B) {

das ist ein potentieller Fehler

von Tim T. (tim_taylor) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Walter S. schrieb:
> Tim T. schrieb:
>> if (temp == B) {
>
> das ist ein potentieller Fehler

Klar, aber solange die Zahlen nur addiert werden tritt das double 
Genauigkeitsproblem nicht auf. War wie geschrieben nur aus dem 
Rückenmark und ich hätte sonst auch eher Festkommazahlen genommen aber 
wayne...

Ansonsten wenn du besser schlafen willst:
1
if (abs(B-temp)<0.01) { blub }

oder auch
1
if ( (B-temp)<0.01) || (temp-B)<0.01) )  { blub }

: Bearbeitet durch User
von Yalu X. (yalu) (Moderator)


Bewertung
1 lesenswert
nicht lesenswert
Tim T. schrieb:
> Klar, aber solange die Zahlen nur addiert werden tritt das double
> Genauigkeitsproblem nicht auf.

Dann lass dein Programm mal mit diesen (scheinbar trivialen) Werten
laufen:
1
  double auswahl[] = {0.2, 0.1};
2
  double B = 0.3;

> if (abs(B-temp)<0.01) { blub }

Nimm fabs statt abs.

> if ( (B-temp)<0.01) || (temp-B)<0.01) )  { blub }

Nimm && statt ||.

Ok, genug gemeckert für den Moment. Ein Beispiel, wo die Fehlerschwelle
von 0.01 zu groß ist, spare ich mir jetzt ;-)

von Tim T. (tim_taylor) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Tim T. schrieb:
>> Klar, aber solange die Zahlen nur addiert werden tritt das double
>> Genauigkeitsproblem nicht auf.
>
> Dann lass dein Programm mal mit diesen (scheinbar trivialen) Werten
> laufen:
>
>
1
>   double auswahl[] = {0.2, 0.1};
2
>   double B = 0.3;
3
>
Hmpf, war bislang davon ausgegangen das die Rundungsfehler sich bei 
Addition ebenfalls addieren und somit 0.2+(Rundungsfehler) + 
0.1+(Rundungsfehler) == 0.3+(Rundungsfehler) ergibt. Tatsächlich bleibt 
eine Abweichung von 5.551115e-017 die dafür sorgt das es in die Hose 
geht. Aber klar, 0.1 und 0.2 haben nach IEEE754 die gleiche Mantisse und 
demnach auch den gleichen normalisierten Rundungsfehler, 0.3 hat eine 
andere Mantisse und demnach auch einen anderen normalisierten 
Rundungsfehler. (Irgendwie kommen gerade doch einige Erinnerungen an 
IEEE754 irgendwo aus dem Grundstudium wieder...)

>
>> if (abs(B-temp)<0.01) { blub }
>
> Nimm fabs statt abs.
Ja, die Feinheiten zwischen C und C++.

>
>> if ( (B-temp)<0.01) || (temp-B)<0.01) )  { blub }
>
> Nimm && statt ||.
>
Bäh stimmt, sollte schon beides erfüllt sein^^.

Dieser Beitrag ist gesperrt und kann nicht beantwortet werden.