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

[Peter (Gast)]

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

[Olmau (Gast)]

Wieso dringend? Finde ich ziemlich frech.

[Peter (Gast)]

Ist dringend, bitte schnell antworten.

[radiostar (Gast)]

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

[Peter (Gast)]

Ist dringend, bitte nicht ablenken und schnell antworten.

[Christian M. (Gast)]

Bist Du mitten in einer Prüfung?

Gruss Chregu

[Joe S. (joesch)]

Ne, wahrscheinlich auf der Toilette. Die Prüfung ist woanders. :)

[Peter (Gast)]

Bitte nicht ablenken sondern antworten.

[Dirk B. (dirkb2)]

Z1, Z3 und Z8, wenn B 42 ist

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

[Achim H. (anymouse)]

Rucksack-Problem ?

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

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

[Peter (Gast)]

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.

[Verweigerer (Gast)]

Nein!

[Berufsberater (Gast)]

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.

[Dirk B. (dirkb2)]

Verweigerer schrieb:
> Nein!

Doch!

[Helmut L. (helmi1)]

Der will doch Cheffe werden und uebt schon mal das deligieren von 
Aufgaben.

[aGast (Gast)]

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.

[Peter (Gast)]

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.

[oder... (Gast)]

Helmut L. schrieb:
> Der will doch Cheffe werden [...]


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

[Klaus Dieter (Gast)]

Du stellst irgendwie wirre Fragen.

[oder... (Gast)]

Bitte nicht ablenken sondern antworten.

[vorticon (Gast)]

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...

[Olmau (Gast)]

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.

[vorticon (Gast)]

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?

[Berufsberater (Gast)]

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.

[Markus W. (dl8mby)]

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

[Peter (Gast)]

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.

[vorticon (Gast)]

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.

[Peter (Gast)]

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.

[Berufsberater (Gast)]

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.

[vorticon (Gast)]

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

[Peter (Gast)]

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
.

[Markus W. (dl8mby)]

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

[Markus W. (dl8mby)]

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

[vorticon (Gast)]

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

[Markus W. (dl8mby)]

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

[brainfuck (Gast)]

Der Peter hat es auf den Punkt gebracht.
Danke Peter

[Markus W. (dl8mby)]

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 [e-mail]
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

[vorticon (Gast)]

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

[Tim T. (tim_taylor)]

Aus dem Rückenmark:

int main(void) {
 double auswahl[] = {1.2, 4.5, 3.4, 10.2};
 double B = 4.6;
 double temp;

 int zahlen = (sizeof(auswahl)/sizeof(double));
 int i,j;
 
 for (i=0; i<2<<(zahlen-1); i++) {
  temp = 0;
  for (j=0; j<zahlen; j++) temp+=auswahl[j]*((i>>j) & 1);
  if (temp == B) {
   for (j=0; j<zahlen; j++) printf("(%2.1f*%d)+", auswahl[j], ((i>>j) & 1));  
   printf("\b = %2.1f\n", B);
  }
 }
  
 return 0;
}

[Pete K. (pete77)]

Dann ist die Hausaufgabe ja gemacht und Peter kann spielen gehen.

[Tim T. (tim_taylor)]

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

[Markus W. (dl8mby)]

Und der zugehörige Output

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

Markus

[Yalu X. (yalu) (Moderator)]

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:

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 :)

[Mike B. (mike_b97)]

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

...

Ist das Brainfuck?

[MikeH (Gast)]

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.

[MikeH (Gast)]

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

[Walter S. (avatar)]

Tim T. schrieb:
> if (temp == B) {

das ist ein potentieller Fehler

[Tim T. (tim_taylor)]

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:

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

oder auch

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

[Yalu X. (yalu) (Moderator)]

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:

  double auswahl[] = {0.2, 0.1};
  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 ;-)

[Tim T. (tim_taylor)]

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:
>
>

>   double auswahl[] = {0.2, 0.1};
>   double B = 0.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^^.