Obstmarkt für Intellektuelle

Bitte aktiviere JavaScript!
A

Anzeige


Vielleicht hilft dir dieser Kurs hier weiter: (hier klicken)
@kneitzel durch 100 oder 10 zu teilen ist schon sinnvoll....
Ich hatte etwas mit dynamischer Programmierung probiert, aber das ist hierbei ga nicht sinnvoll. :rolleyes: Oder ich habe etwas entdeckt was noch keiner entdeckt hat, aber das halte ich für sehr sehr unwahrscheinlich. :D
 
@kneitzel durch 100 oder 10 zu teilen ist schon sinnvoll....
Genau das sehe ich nicht. Zumindest nicht ohne weitere Checks. Selbst wenn du nur 10er Schritte nimmst, dann baue ich dir ein Beispiel mit einem Ergebnis, bei dem eine Zahl hinten eine 5 hat oder so.

Der experimentelle Ansatz benötigt hier schon die vollen Schritte. Die einzige Optimierung wäre evtl, dass man die Schleife abbricht, wenn man bereits zu hoch ist bei einer Berechnung, denn durch weiteres Erhöhen in der Schleife wird es ja nur noch größer ....
Die Optimierung für diese Aufgabe ist wie die Aufgabe selbst konstant.
Java:
public static int[] getSolution() {
       return new int[] { 100, 200, 300 };
}
:p
Das war ja nie in Zweifel gezogen und war ja schon längst im Thread gesagt.
Aber das ändert ja nichts an der Tatsache, dass die vorgeschlagene Optimierung entweder falsch ist oder nicht ausreichend gut beschrieben, denn ich habe dann diese bisher falsch verstanden....
 
Das war ja nie in Zweifel gezogen und war ja schon längst im Thread gesagt.
Aber das ändert ja nichts an der Tatsache, dass die vorgeschlagene Optimierung entweder falsch ist oder nicht ausreichend gut beschrieben, denn ich habe dann diese bisher falsch verstanden....
Dem habe ich ja nicht widersprochen. Wenn Du genau hinsiehst, wirst Du feststellen, dass Du für Deine Bemerkung von mir ein Like erhalten hattest. Meine Anmerkung dazu war nur wenn schon Optimierung dann gleich eine konstante, da das Programm ja keine Eingabedaten erwartet. ;) (dir geht's wie Sheldon bei Big Bang Sarkasmus oder nicht ?)
 
Also Bitte Bang Theory kenne ich nicht (außer hin und wieder was man an Werbung mitbekommt). Wie geht es denn Sheldon bei Sarkasmus?
 
@kneitzel hier nicht optimieren zu wollen ist blöd... Es kann klar gesagt werden, wann verlustlos durch 10, 100 usw geteilt werden kann...

@Blender3D Sheldon hätte noch Fragen müssen, wem gegenüber der Sarkasmus gilt...

aber ich denke ihr möchtet mich gar nicht verstehen.
 
@kneitzel hier nicht optimieren zu wollen ist blöd... Es kann klar gesagt werden, wann verlustlos durch 10, 100 usw geteilt werden kann...

@Blender3D Sheldon hätte noch Fragen müssen, wem gegenüber der Sarkasmus gilt...

aber ich denke ihr möchtet mich gar nicht verstehen.
Wenn ich Dich nicht verstehen wollte, dann würde ich nicht fragen.

Und woran erkennst Du, durch was Du teilen kannst? Das will ich eben wissen / verstehen. Das ist eben.nicht ganz so trivial meine ich.
 
Wenn ich Dich nicht verstehen wollte, dann würde ich nicht fragen.

Und woran erkennst Du, durch was Du teilen kannst? Das will ich eben wissen / verstehen. Das ist eben.nicht ganz so trivial meine ich.
Also das mit dem trivial ziehe ich zurück, natürlich ist es trivial:
Lösen des Gleichungssystems und dann den größten gemeinsamen Teiler ermitteln.

Aber ich meinte halt, ohne die Aufgabe ansatzweise schon zu lösen.
 
hier nicht optimieren zu wollen ist blöd... Es kann klar gesagt werden, wann verlustlos durch 10, 100 usw geteilt werden kann...
Es handelt sich ja um Gleichungen, in dem Fall muss was auf der einen Seite getan wird auch auf der anderen erfolgen:
a = b
<=> a/100 = b/100
Somit wäre folgendes falsch:
A + 2B + 3G = 1400
<=> A + 2B + 3G = 14
Hingegen folgendes richtig:
A + 2B + 3G = 1400
<=> A/100 + 2B/100 + 3G/100 = 14

Was aus meiner Sicht in dem Fall jedoch keine Optimierung darstellt

Oder liege ich jetzt daneben? ;)
 
Es handelt sich ja um Gleichungen, in dem Fall muss was auf der einen Seite getan wird auch auf der anderen erfolgen:
a = b
<=> a/100 = b/100
Somit wäre folgendes falsch:
A + 2B + 3G = 1400
<=> A + 2B + 3G = 14
Hingegen folgendes richtig:
A + 2B + 3G = 1400
<=> A/100 + 2B/100 + 3G/100 = 14

Was aus meiner Sicht in dem Fall jedoch keine Optimierung darstellt

Oder liege ich jetzt daneben? ;)
Es geht um den Brute-Force-Ansatz, welcher alle Möglichkeiten durchprobiert. Dann hätte man nur 5^3 = 125 Möglichkeiten zu überprüfen im Vergleich zu 500^3 = 125000000.
Da aber @Tobias-nrw bisher keine Begründung geliefert hat, warum man diese Annahme treffen kann, ohne die Lösung zu kennen, glaub ich nicht das da noch was kommt. :D
Desweiteren muss man bei dieser "Optimierung" aufpassen, da man an dieser Stelle die Interger-Arithmetik verlässt und mit 'ungenauer' Gleitkomma-Arithmetik arbeitet.

@kneitzel : Eine kleine Vereinfachung, die man vielleicht "sehen" kann, könnte so aussehen:

Untersuche, welche Variable gerade oder ungerade sein kann:
Die letzte Gleichung 5A+B+C = 1000 mod 2 => A+B+C = 0 mod 2, d.h. entweder alle drei sind gerade oder genau eine ist gerade und die anderen beiden ungerade.
Betrachte den zweiten Fall, dann gibt es die Möglichkeiten: (A,B ungerade, C gerade) oder (A,C ungerade, B gerade) oder (B,C ungerade, A gerade)
1. Möglichkeit: Wegen der ersten Gleichung ist diese Möglichkeit ausgeschlossen, da 1*1 + 2*1 + 3*0 = 1 != 0 mod 2
2. Möglichkeit: Wegen der zweiten Gleichung ist diese Möglichkeit ausgeschlossen, da 2*1+3*0+5*1 = 1 != 0 mod 2
3. Möglichkeit: Wegen der ersten Gleichung ist diese Möglichkeit ausgeschlossen, da 1*0+2*1+3*1 = 1 != 0 mod 2

Also folgt: Der zweite Fall kann nicht vorkommen, somit müssen nur gerade A,B und C getestet werden.

Letztlich habe ich gerade das Gleichungssystem im Körper F_2 gelöst, deshalb ist das nicht wirklich ein "schnellerer" Weg. Man wohl auch gleich das komplette System mit Gauß/LR-Zerlegung lösen können :D. (Dennoch: Mit diesem Wissen muss man nur noch 250^3 = 15625000 Belegungen von A,B,C testen, das ist nur ein Achtel aller Möglichkeiten. )
 
Es handelt sich ja um Gleichungen, in dem Fall muss was auf der einen Seite getan wird auch auf der anderen erfolgen:
a = b
<=> a/100 = b/100
Somit wäre folgendes falsch:
A + 2B + 3G = 1400
<=> A + 2B + 3G = 14
Hingegen folgendes richtig:
A + 2B + 3G = 1400
<=> A/100 + 2B/100 + 3G/100 = 14

Was aus meiner Sicht in dem Fall jedoch keine Optimierung darstellt

Oder liege ich jetzt daneben? ;)
Du liegst genau richtig. Du kannst gerne a/100 durch a' und b/100 durch b' und g/100 durch g' ersetzen, so dass du
a' + 2b' + 3g' = 14 erhälst.

Dies ist aber keine Optimierung, denn was nicht explizit gesagt wurde ist:
Bei a, b und g handelt es sich um positive, ganze Zahlen, d.h. Schrittweite 1 ist richtig.
a', b' und g' sind jetzt natürlich keine positiven, ganze Zahlen mehr. Und aus der oben angegebenen Formel wird deutlich: Hier muss die Schrittweite dann 0,01 sein.
 
Da aber @Tobias-nrw bisher keine Begründung geliefert hat, warum man diese Annahme treffen kann, ohne die Lösung zu kennen, glaub ich nicht das da noch was kommt
Als Begründung sollte das Verfahren langen....
Java:
public class Obste {
    int[] rechne(int[][] cents) {
        int n1 = cents.length;
        int n2 = cents[0].length;
        int[] i = new int[n1];
        for (int j = 0;;) {
            boolean[] a = new boolean[n1];
            for (int k = 0; k < n1; k++) {
                int l = 0;
                for (int m = 0; m < n1; m++) {
                    l = l + cents[k][m] * i[m];
                }
                a[k] = l == cents[k][n1];
            }
            boolean c = true;
            for (boolean b : a) {
                c = c && b;
            }
            if (c) {
                return i;
            }
            i[j]++;
            j++;
            if (j == n1) {
                j--;
                while (i[j] == 500) {
                    i[j] = 0;
                    j--;
                }
            }
        }
    }
    public static void main(String[] args) {
        Obste o = new Obste();

        int[] rechne = o.rechne(new int[][]{{1, 2, 3, 1400}, {2, 3, 5, 2300}, {5, 1, 1, 1000}});
        for (int i = 0; i < rechne.length; i++) {
            System.out.println((i + 1) + ". kostet " + rechne[i]);
        }

        rechne = o.rechne(new int[][]{{1, 2, 3, 140}, {2, 3, 5, 230}, {5, 1, 1, 100}});
        for (int i = 0; i < rechne.length; i++) {
            System.out.println((i + 1) + ". kostet " + rechne[i]);
        }

        rechne = o.rechne(new int[][]{{1, 2, 3, 14}, {2, 3, 5, 23}, {5, 1, 1, 10}});
        for (int i = 0; i < rechne.length; i++) {
            System.out.println((i + 1) + ". kostet " + rechne[i]);
        }
    }
}

Am ergebnis sieht man dann das es stimmt. (n2 braucht man in dem Fall net)
 
Es geht um den Brute-Force-Ansatz, welcher alle Möglichkeiten durchprobiert. Dann hätte man nur 5^3 = 125 Möglichkeiten zu überprüfen im Vergleich zu 500^3 = 125000000.
Da aber @Tobias-nrw bisher keine Begründung geliefert hat, warum man diese Annahme treffen kann, ohne die Lösung zu kennen, glaub ich nicht das da noch was kommt. :D
Desweiteren muss man bei dieser "Optimierung" aufpassen, da man an dieser Stelle die Interger-Arithmetik verlässt und mit 'ungenauer' Gleitkomma-Arithmetik arbeitet.

@kneitzel : Eine kleine Vereinfachung, die man vielleicht "sehen" kann, könnte so aussehen:

Untersuche, welche Variable gerade oder ungerade sein kann:
Die letzte Gleichung 5A+B+C = 1000 mod 2 => A+B+C = 0 mod 2, d.h. entweder alle drei sind gerade oder genau eine ist gerade und die anderen beiden ungerade.
Betrachte den zweiten Fall, dann gibt es die Möglichkeiten: (A,B ungerade, C gerade) oder (A,C ungerade, B gerade) oder (B,C ungerade, A gerade)
1. Möglichkeit: Wegen der ersten Gleichung ist diese Möglichkeit ausgeschlossen, da 1*1 + 2*1 + 3*0 = 1 != 0 mod 2
2. Möglichkeit: Wegen der zweiten Gleichung ist diese Möglichkeit ausgeschlossen, da 2*1+3*0+5*1 = 1 != 0 mod 2
3. Möglichkeit: Wegen der ersten Gleichung ist diese Möglichkeit ausgeschlossen, da 1*0+2*1+3*1 = 1 != 0 mod 2

Also folgt: Der zweite Fall kann nicht vorkommen, somit müssen nur gerade A,B und C getestet werden.

Letztlich habe ich gerade das Gleichungssystem im Körper F_2 gelöst, deshalb ist das nicht wirklich ein "schnellerer" Weg. Man wohl auch gleich das komplette System mit Gauß/LR-Zerlegung lösen können :D. (Dennoch: Mit diesem Wissen muss man nur noch 250^3 = 15625000 Belegungen von A,B,C testen, das ist nur ein Achtel aller Möglichkeiten. )
Nunja, da die Schrittweite natürlich auch angepasst werden muss, ist das natürlich erst einmal nicht wirklich interessant und die Schrittanzahl würde konstant bleiben.

Ich habe über diese Thematik viel nachgedacht und Dein Ansatz mit dem gerade ist mir auch durch den Kopf gegangen.

Man kann ja a, b und g durch a'*x, b'*x und g'*x ersetzen mit der Annahme, dass a',b', g' und x ganze, positive Zahlen sind. Dann würde man erhalten:
a'x + 2 b'x + 3 g'x = 1400
(a' + 2b' + 3g') *x = 1400
a' + 2b' +3g' = 1400 / x

Das Geiche dann auch noch für die anderen Gleichungen, so dass man dann am Ende 3 Gleichungen mit 4 Unbekannten hat.
Die kann man aber dann umformen und schauen, ob man hier auf Anhieb x finden kann. Das mit dem Gerade / Ungerade ist nicht schlecht. Das geht aber auch nur, weil die Zahlen ein vielfaches von 100 sind und damit die 100 als Teiler sich förmlich aufzwängt.

Aber: Um ein x zu verifizieren benötigt man unter dem Strich auch wieder die Lösung. Und durch das Gleichungssystem mit den 4 Unbekannten wird auch direkt deutlich: Diese Brute Force Optimierung mag mathematisch interessant sein, aber für die Praxis hat diese keine Relevanz.

Die einzige Optimierung, die ich machen würde (Wenn die Gleichungen abgewandelt sein dürften):
- ich würde die Gleichung so umstellen (a, b, g ggf. vertauschen), so dass die innere Schleife die Betragsmäßig größte Zahl hat. (Wäre hier g, denn da ist die 5 der höchste Faktor)
- Ich würde die innere Schleife bei positiven Faktor (ist hier ja gegeben) von 0...500 laufen lassen. Ansonsten von 500...0.
- Ich würde die Formeln separat prüfen. Alle Formeln mit dem notwendigen Vorzeichen bilden ein Abbruchkriterium:
Bei uns ist dies bei allen Formeln gegeben, denn alle Faktoren sind positiv. Wenn also bei Prüfung in der Schleife das Ergebnis schon zu hoch ist, dann muss ich nicht weiter hoch zählen! Also z.B. a = 1, b=1 g = 466:
1 + 2*1 + 3*466 = 1401 -> größer als 1400. Es macht hier keinen Sinn mehr, 467, 468, ... zu prüfen ...
 
Als Begründung sollte das Verfahren langen....
Also ich will Dir nicht zu nahe treten, aber ich verstehe diesen Code nicht auf Anhieb. Evtl. wird der Code verständlicher, wenn Du alle Variablen durch UUIDs ersetzt ... dann sind sie länger als 1 Zeichen und damit doch bestimmt besser verständlich ....

Deine Optimierung hatte ich so verstanden, dass Du die Schrittgröße angepasst haben wolltest (statt 1 eben 100). Dies wäre in dem Beispiel ok gewesen, aber woran hast Du es erkannt?

An den Ergebnissen (jeweils durch 100 teilbar) kann man es nicht erkennen, wie ich durch ein alternatives Beispiel gezeigt habe.

Das ist die eigentliche Frage. Dein neues Verfahren macht irgendwas, was sehe ich nicht auf Anhieb. Aber ich habe nicht vor, einen sehr Kryptisch geschriebenen Code verstehen zu wollen nur um dann zu rätseln, was das bezüglich Deiner Aussage zur notwendigen Schrittweite besagen soll.
 
Na dann lass es, niemand zwingt Dich meinen Code zu verstehen :)
Natürlich nicht, aber dennoch interessiert mich, was für eine Optimierung Du gesehen hast. Wie willst Du die Schrittweite optimieren? Wie erkennst Du, auf was Du optimieren willst/kannst? Denn Deine Aussage war ja: "Wieso reduzierst Du Deine Schleifendurchläufe denn nicht auf ein Hundertstel, wie ich es geschrieben habe?"
Klar, aus den Ergebnissen kann man das ablesen - das habe ich ja auch schon ausführlich erläutert. Nur eben geht es ja darum, dass man die Ergebnisse per brute force ermitteln will.

Machen wir es allgemeiner. Es gilt:
e11 * a + e21 * b * e31 * g = e41
e13 * a + e22 * b * e32 * g = e42
e13 * a + e23 * b * e33 * g = e43

Also die eXX Werte werden eingegeben bei Programmstart und es sollen mögliche Preise für Äpfel (a), Birnen (b) und Grapefruit (g) ermittelt werden über einen Brute Force Algorithmus.
e1X sind dabei die Anzahl der Äpfel
e2X sind dabei die Anzahl der Birnen
e3X sind dabei die Anzahl der Grapefruit
e4X ist dabei der Gesamtpreis in Cent.

Es wird noch gp eingegeben - der maximale Preis von den Obstsorten in Cent. Und natürlich kostet jedes Obststück einen Betrag in Cent ohne Nachkommastellen (Also nicht wie z.B. bei Benzin wo noch 1/10 Cent im Preis angegeben sind.

Wo und wie kommt hier Deine Optimierung der Schrittweite? Wenn Du hier einen einfachen Ansatz sehen solltest, dann würde mich das interessieren. (Ohne die Gleichungen aufzulösen d.h. ohne im Endeffekt die Ergebnisse zu nutzen. Ansonsten wäre klar: Man kann die Schrittweite auf den größten gemeinsamen Teiler von a, b und c setzen ... e4x muss man nicht mehr prüfen.

Eine Optimierung, die ich sehe: Man kann ggf. den GGT von e11 - e33 ermitteln. Dann hätte man das als Schrittweite....
 
Ich war noch nicht so weit die Schrittweite im brute force zu optimieren, aber wenn man so will könnte man mit zum Besenstiel 10_000, 1_000 usw. usf anfangen, bis man keine 0-Werte erhält. Der geringere Mehraufwand (es gibt ein paar mehr Schleifendurchläufe) wäre dabei zu vernachlässigen, imo. Brute force um brute force herum so zu sagen.
 
Naja man darf aber nicht vergessen, das es hier um das Lösen eines simplen LGS' geht... Dafür gibt es Verfahren >en masse<... Und alle Verfahren mit 0-Aufwand sind in jedem Fall den Verfahren des kubischen Aufwands vorzuziehen. Sprich Äpfel != Birnen, Äpfel != Grapefruits und Birnen != Gräpefruits... Im übertragenen Sinne ist es schwer ein totes Pferd zu reiten. :rolleyes:
 
Im übertragenen Sinne ist es schwer ein totes Pferd zu reiten
Du hast recht! Man könnte hier auch die Metapher "Um des Kaisers Bart streiten." verwenden.
Eine Optimierung für ein in diesem Kontext grundsätzlich zu aufwändiges Verfahren zu suchen macht keinen Sinn.
Wenn man optimieren will dann gleich analytisch.
Für die Brutforce Variante kann man höchstens den von mir erwähnten sofortigen Abbruch bei Erfolg erwähnen. Siehe Post #20
Es ist nämlich ein grundsätzlicher Fehler ein Verfahren ohne Nutzen nach Erfolg weiterlaufen zu lassen.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben