Permutation < Softwaretechnik+Pro < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:19 Mi 14.11.2012 | | Autor: | Permutex |
| Aufgabe | Programmieren einer Schleife oä um alle Kombinationsmöglickeiten für folgendes Problem zu bekommen:
Ein Schrank hat 7 Fächer. Jedes Fach soll mit mindesten 1Kg beladen sein. Das Gesamtgewicht des Schrankes soll 60Kg nicht überschreiten, darf aber bis zum Mindestgewicht von 7*1kg absinken. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich bin auf der Suche nach einer möglichst effektiven und allgemeinen Art die obige Fragestellung zu lösen.
Ich habe mir bei wiki uä die Formeln zur Kombinatorik angeschaut, aber nicht so richtig das passende gefunden.
Wie lässt sich eigentlich die Anzahl der möglichen Kombinationen errechnen? Mit Fakultät ist es da ja nicht mehr getan oder?
Ich möchte ein Excelblatt programmieren (VBA) um eine Matrix zu erhalten in der alle Kombinationsmöglichkeiten enthalten sind.
Bin für jeden Denkanstoß in die richtige Richtung dankbar.
Grüße,
Permutex
Dateianhänge:
Anhang Nr. 1 (Typ: xls) [nicht öffentlich]
|
|
| |
|
Hallo Permutex, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Programmieren einer Schleife oä um alle
> Kombinationsmöglickeiten für folgendes Problem zu
> bekommen:
>
> Ein Schrank hat 7 Fächer. Jedes Fach soll mit mindesten
> 1Kg beladen sein. Das Gesamtgewicht des Schrankes soll 60Kg
> nicht überschreiten, darf aber bis zum Mindestgewicht von
> 7*1kg absinken.
Ich gehe mangels weiterer Information davon aus, dass das Gewicht nur kiloweise verteilt werden kann, also z.B. nicht 3500g in einer Schublade liegen können.
> ich bin auf der Suche nach einer möglichst effektiven und
> allgemeinen Art die obige Fragestellung zu lösen.
> Ich habe mir bei wiki uä die Formeln zur Kombinatorik
> angeschaut, aber nicht so richtig das passende gefunden.
>
> Wie lässt sich eigentlich die Anzahl der möglichen
> Kombinationen errechnen? Mit Fakultät ist es da ja nicht
> mehr getan oder?
>
> Ich möchte ein Excelblatt programmieren (VBA) um eine
> Matrix zu erhalten in der alle Kombinationsmöglichkeiten
> enthalten sind.
Das dürfte die Möglichkeiten von Excel sprengen.
Es gibt hier immerhin [mm] \vektor{60\\53}=386.206.920 [/mm] Kombinationen.
> Bin für jeden Denkanstoß in die richtige Richtung
> dankbar.
Ich dachte, es ginge um die Programmierung an sich. Wenn es nur diese Aufgabe ist, dann weißt Du ja jetzt den ungefähren Rechenaufwand.
Die Herleitung ist etwas mühsam, aber wenn Du sie unbedingt brauchst, kann ich sie grob skizzieren.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:18 Mi 14.11.2012 | | Autor: | Permutex |
Hallo reverend!
Das ist ja mann ne Zahl. Das es viel ist habe ich mir schon gedacht, aber so viel.
Auf jeden fall bin ich an der Herleitung interessiert!
Wie geht denn die Schrittweite (1kg wie Du richtig angenommen hast) ein? Quadratisch, kubisch ..?? Mit anderen Worten, wieviele Möglichkeiten hätte ich denn bei 2kg Schrittweite?
An der Programmtechnischen Umsetzung bin ich ebenfalls interessiert. Als Sprachen würde ich C++ bzv VBA bevorzugen.
Danke und Grüße,
Permutex
|
|
|
| |
|
Hallo Permutex,
ich habe erst jetzt bemerkt, dass Du da schon reagiert hast.
Du hast Deine erste Frage wieder eröffnet. Das mögen wir hier nicht so gerne, jedenfalls nicht ohne Nachricht, warum. Es signalisiert den bisherigen Antwortgebern (also zZ nur mir), dass ihre Antwort wertlos ist.
Besser ist, Du stellst einfach eine neue Frage.
Da Du aber neu hier bis, habe ich einfach mal ein bisschen herumoperiert und Die erste Frage wieder auf beantwortet gestellt, Deine Mitteilung zur Frage umgewandelt, und antworte nun darauf. Schließlich willst Du ja wissen, wie ich zu meiner Antwort gekommen bin.
> Hallo reverend!
>
> Das ist ja mann ne Zahl. Das es viel ist habe ich mir schon
> gedacht, aber so viel.
>
> Auf jeden fall bin ich an der Herleitung interessiert!
>
> Wie geht denn die Schrittweite (1kg wie Du richtig
> angenommen hast) ein? Quadratisch, kubisch ..?? Mit anderen
> Worten, wieviele Möglichkeiten hätte ich denn bei 2kg
> Schrittweite?
Nein, irgendwie "fakultativ". 
2kg Schrittweite gehen nur dann auf, wenn in jeder Schublade mindestens auch 2kg liegen bzw. in einer geraden Anzahl von Schubladen eine ungerade Zahl von kg. Das ist deutlich komplizierter...
Einfacher wäre es allerdings, wenn man z.B. in 500g- oder 250g- Schritten vorginge. Aber auch das musst Du Dir erstmal selbst herleiten, wenn Du die folgende Vorgehensweise verstanden hast. Mir ist es gerade zuviel Arbeit, zumal für eine "akademische" Frage.
> An der Programmtechnischen Umsetzung bin ich ebenfalls
> interessiert. Als Sprachen würde ich C++ bzv VBA
> bevorzugen.
Hm. Ich kann Dir wohl nur Pseudocode anbieten, also die logische Struktur einer Programmierung. Die Übersetzung in eine reale Programmiersprache sollte dann aber nicht mehr schwerfallen.
Auch das aber vielleicht morgen. Für heute nehme ich mir "nur noch" die Herleitung der Zahl der Möglichkeiten vor.
Es geht darum, max. 60kg kiloweise so zu verteilen, dass in keiner der 7 Schubladen weniger als 1kg liegt. Weitere Einschränkungen scheint es ja nicht zu geben. In der Aufgabe scheint der Schrank als gewichtslos vorausgesetzt zu werden. Meinetwegen. Das Gewicht des Schrankes (physikalisch korrekt wäre: seine Masse) wird also als "Tara" unbeachtet gelassen.
Legen wir also erst einmal 1kg in jede Schublade. Das muss ja da sein und steht nicht mehr zur Diskussion. Dazu können jetzt noch max. 53kg Last kommen, in beliebiger Verteilung.
Wenn 0kg zusätzlich verteilt werden, gibt es nur 1 Möglichkeit. Es kommt eben zur Grundverteilung von 1kg pro Schublade nichts dazu.
Wenn 1kg zusätzlich verteilt werden, gibt es 7 Möglichkeiten. Bis dahin geht das ja noch leicht und übersichtlich im Kopf zu rechnen und ist leicht zu überblicken. Ab da wird es schwierig.
Also werden wir mal allgemein.
Es sind n[kg] auf die 7 Schubladen zu verteilen, und es nicht egal, in welcher Weise das geschieht. n-6,1,1,1,1,1,1 ist also etwas anderes als 1,1,1,n-6,1,1,1 und auch als 0,0,0,0,0,0,n.
Das löst man, indem man den n[kg] noch 6 "Trenner" zugibt, Grenzmarkierungen sozusagen. Dann gibt es (n+6) Plätze, wo die Trenner prinzipiell liegen können, und dafür gibt es [mm] \vektor{n+6\\6} [/mm] Möglichkeiten.
Alles, was also zu tun bleibt ist, diese Möglichkeiten für alle möglichen n aufzusummieren. Und die möglichen n gehen hier von 0 bis 53. Sieben Kilo liegen ja schon in den Schubladen.
Also, endlich mal mathematisch notiert, gibt es folgendes zu lösen:
[mm] \summe_{n=0}^{53}\vektor{n+6\\6}.
[/mm]
Dafür gibt es eine Formel, auf die Du aber nicht einfach zurückgreifen darfst. Du musst sie selbst beweisen, kombinatorisch oder per vollständiger Induktion. Ich würde allein deswegen Letzteres bevorzugen, weil ich keine Ahnung habe, wie man das kombinatorisch herleitet. Vielleicht hat da ja jemand noch eine Idee, ich habe gerade keine.
Die Formel lautet für ein festes N: [mm]\blue{\summe_{k=0}^{m}\vektor{N+k\\
N}=\vektor{N+m+1\\
m}}[/mm].
Damit ist in der vorliegenden Aufgabe also für N=6 (Zahl der "Trenner") zu berechnen:
[mm] \summe_{k=0}^{53}\vektor{6+k\\6}=\vektor{6+53+1\\53}=\vektor{60\\53}=386.206.920
[/mm]
Eine Programmlösung wird also voraussichtlich 53 Verschachtelungen/Rekursionen beinhalten.
Soviel für jetzt. Ich weiß noch nicht, ob ich vor morgen Abend dazu komme, Fragen zu beantworten bzw. Hinweise zur Programmierung zu geben.
Der Vorteil eines Forums ist aber, dass ich das auch gar nicht muss. Hier sind ja noch mehr Leute unterwegs, die das können.
Bis dahin also erstmal gutes Gelingen beim Nachvollziehen und Beweisen der blauen Formel. Ich hoffe, ich habe nicht zu viele Irrtümer eingebaut. Es ist schließlich schon spät...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:47 Do 15.11.2012 | | Autor: | Permutex |
Moin!
Vielen Dank schon mal für Deine Arbeit.
Irgenwas scheint noch nicht ganz io zu sein. Wenn ich 8kg maximaltotalmasse annehme, habe ich 7 Möglichkeiten. Die 2 kg wandern von Fach zu Fach, also 7 mal. Die von Dir vorgeschlagene Formel ergibt 8 Möglichkeiten. Im Anhang eine kurze Exceltabelle die dies wiedergibt.
Die ganze Aufgabe ist natürlich ziemlich Theoretisch angehaucht, hat jedoch einen Zweck. (Sinn will ich in diesem Zusammenhang nicht sagen )
Für diesen Schrank soll eine Parameterstudie durchgeführt werden. Eine Rechnung dauert ca 45sec. Deshalb sind natürlich nur eine Begrenzte Anzahl Rechnungen möglich. (oder ich miete mich auf dem Titan Rechner der Amerikaner ein).
Schlußziel ist es also herauszufinden, bei welcher Kiloschrittweite eine noch vertretbare Anzahl von Rechnungen nötig ist.
Gut währe deshalb, wenn in der Formel für die Anzahl der möglichen Kombinationen, auch die Schrittweite mit eingeht.
Wenn mann dann eine realistsiche Anzahl Rechnungen hat, muß ich mir "nur" noch eine Kopf darüber machen, wie man die Eigentliche Verteilungsmatrix erstellt (Programmiertechnisch).
Also nochmals vielen Dank schon mal für Deine Antwort und hoffentlich bis bald.
Grüße Permutex
Dateianhänge:
Anhang Nr. 1 (Typ: xlsx) [nicht öffentlich]
|
|
|
| |
|
Moin,
> Vielen Dank schon mal für Deine Arbeit.
> Irgenwas scheint noch nicht ganz io zu sein. Wenn ich 8kg
> maximaltotalmasse annehme, habe ich 7 Möglichkeiten. Die 2
> kg wandern von Fach zu Fach, also 7 mal. Die von Dir
> vorgeschlagene Formel ergibt 8 Möglichkeiten. Im Anhang
> eine kurze Exceltabelle die dies wiedergibt.
Ja, es ist eine Summenformel. Zu den 7 Möglichkeiten kommt bei mir noch die 1 Möglichkeit, die sich bei nur 7 kg ergibt.
> Die ganze Aufgabe ist natürlich ziemlich Theoretisch
> angehaucht, hat jedoch einen Zweck. (Sinn will ich in
> diesem Zusammenhang nicht sagen )
> Für diesen Schrank soll eine Parameterstudie
> durchgeführt werden. Eine Rechnung dauert ca 45sec.
> Deshalb sind natürlich nur eine Begrenzte Anzahl
> Rechnungen möglich. (oder ich miete mich auf dem Titan
> Rechner der Amerikaner ein).
>
> Schlußziel ist es also herauszufinden, bei welcher
> Kiloschrittweite eine noch vertretbare Anzahl von
> Rechnungen nötig ist.
>
> Gut währe deshalb, wenn in der Formel für die Anzahl der
> möglichen Kombinationen, auch die Schrittweite mit
> eingeht.
Das ist, wie gesagt, nicht so einfach. Abschätzen kannst Du das aber schon mit der vorliegenden Formel, wenn Du einfach eine kleinere Obergrenze annimmst. So wäre bei einer Einteilung in 5kg-Schritte die Zahl sehr klein, weil das natürlich der Obergrenze m=11 entspräche; 12 verschiedene Gewichte, eins fest in jeder Schublade, bleiben also 5, dazu dann die 6 "Trenner". Insgesamt 792 Möglichkeiten.
Bei 3kg-Schritten ist die Obergrenze m=19 dran, und die scheint hier besser: 77.520 Möglichkeiten.
In 2kg-Schritten ist m=29, 2.035.800 Möglichkeiten. Das ist m.E. realistisch.
In 1,5kg-Schritten ist m=39, 18.643.560 Möglichkeiten. Da kommt es dann schon auf die Geschwindigkeit Deines Algorithmus und natürlich des Rechners an.
In 1,2kg-Schritten ist m=49, 99.884.400 Möglichkeiten.
> Wenn mann dann eine realistsiche Anzahl Rechnungen hat,
> muß ich mir "nur" noch eine Kopf darüber machen, wie man
> die Eigentliche Verteilungsmatrix erstellt
> (Programmiertechnisch).
Grüße
reverend
|
|
|
|
