WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Kombinierung von Bauteilen

 

General_Griboz
Forum-Fortgeschrittener

Forum-Fortgeschrittener


Beiträge: 66
Anmeldedatum: 05.04.17
Wohnort: ---
Version: R2016b
     Beitrag Verfasst am: 15.05.2017, 14:15     Titel: Kombinierung von Bauteilen
  Antworten mit Zitat      
Moin,

ich habe folgendes Problem. Ich habe eine Liste von Bauteilen die Kosten besitzen und ich hab ein maximal Budget, dass für Bauteile ausgegeben werden darf. Ich hätte nun alle Kombinationen von Bauteilen, die weniger oder gleich viel Kosten wie das maximal Budget. Eine beispielhafte Tabelle würde so aussehen.

Index Komponenten Kosten
1 Bauteil1 100€
2 Bauteil2 200€
3 Bauteil3 300€
4 Bauteil4 150€

Wenn ich sage, dass mein max Budget 300€ betragen würde, wären mögliche Kombinationen:
1. Bauteil1+Bauteil2
2. Bauteil3
3. Bauteil1+Bauteil4.

Gibt es ein verfahren, mit dem ich praktische jede Kombination solange "auffülle" bis mein max Budget erreicht ist oder gerade darunter liegt ist wie in Kombination 3. Habe mir schon combnk angeuckt, aber da ist das Proble, dass ich mein k wissen muss und das weiß ich am Anfang ja nicht, da ja unterschiedlich viele Bauteile genommen werden können.

Daher die Frage, ob es eine Funktion gibt die mir solche Kombinationen ausgibt oder aber vllt gibt es ja auch einen theoretischen Algorithmus, den ich in matlab implementieren kann.

Vielen Dank im Vorraus.

Gruß
Private Nachricht senden Benutzer-Profile anzeigen


Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 15.05.2017, 15:18     Titel:
  Antworten mit Zitat      
Hallo,

ich würde das rekursiv angehen.

Falls Guthaben > min(Bauteilkosten)
- Schleife über alle Bauteile
-- falls Bauteilkosten < Guthaben
--- kaufe ein Bauteil. Rufe die Funktion rekursiv auf mit (Guthaben - Bauteilkosten)

Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
General_Griboz
Themenstarter

Forum-Fortgeschrittener

Forum-Fortgeschrittener


Beiträge: 66
Anmeldedatum: 05.04.17
Wohnort: ---
Version: R2016b
     Beitrag Verfasst am: 15.05.2017, 15:53     Titel:
  Antworten mit Zitat      
Aber bekomme ich so nicht nur eine Kombination heraus? Ich hätte ja gerne alle Kombinationen, die das Kriterium erfüllen mein Budget nicht zu überschreiten.

Und könntest du vllt auch etwas konkreter werden mit eventuellem Code, denn mit rekuriven Funktionen kenne ich mich noch nicht so gut aus.
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 15.05.2017, 16:09     Titel:
  Antworten mit Zitat      
Hallo,

durch die Schleife bekommst du alle Kombinationen, die das Budget ausreizen. Problem wird eher sein, dass du manche Kombinationen doppelt bekommst. Da kann man sich so behelfen, dass man eine aufsteigende Reihenfolge implementiert.

Zitat:
denn mit rekuriven Funktionen kenne ich mich noch nicht so gut aus.

Der Punkt daran ist, dass die Funktion sich selbst mit einem kleineren Problem aufruft.

Beispiel: ich habe 1000 Euro. Nun kaufe ich ein Bauteil für 300 Euro. Dann habe ich noch 700 Euro, und rufe die Funktion erneut mit diesem kleineren Betrag auf.

Konkreter ginge nur, dass ich es komplett implementiere. Dazu fehlt mir momentan die Zeit.

Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 15.05.2017, 17:24     Titel:
  Antworten mit Zitat      
Hallo,

erster Versuch:
Code:
function kombis = einkaufen(guthaben, preise)

nP = numel(preise);
kombis = zeros(1, nP);

for numK = 1:floor(guthaben/preise(1))
    if nP >= 2
        restEinkauf = einkaufen(guthaben - numK*preise(1), preise(2:end));
    else
        restEinkauf = [];
    end
    iKombis = [numK * ones(size(restEinkauf,1), 1), restEinkauf];
    kombis = [kombis; iKombis];
end


Beispielaufruf:
Code:
kombis = einkaufen(1000, [100:100:400])


Allerdings bin ich mir sicher, ob die Funktion alle Kombinationen erkennt.

Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 15.05.2017, 20:16     Titel:
  Antworten mit Zitat      
Hallo,

jetzt sieht's besser aus.
Code:
function kombis = einkaufen(guthaben, preise)

nP = numel(preise);
kombis = zeros(0, nP);

for numK = 0:floor(guthaben/preise(1))
    if nP >= 2
        if guthaben >= min(preise)
            restEinkauf = einkaufen(guthaben - numK*preise(1), preise(2:end));
        else
            restEinkauf = zeros(1, nP-1);
        end
        iKombis = [numK * ones(size(restEinkauf,1), 1), restEinkauf];
    else
        iKombis = numK;
    end
    kombis = [kombis; iKombis];
end  


Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 15.05.2017, 21:30     Titel:
  Antworten mit Zitat      
... und so gefällt es mir noch besser:

Code:
function kombis = einkaufen(guthaben, preise)

nP = numel(preise);
if nP >= 2
    % mögliche Anzahlen des ersten Bauteils kaufen, und vom Restguthaben die anderen
    kombis = zeros(0, nP);
    for numK = 0:floor(guthaben/preise(1))    
        restEinkauf = einkaufen(guthaben - numK*preise(1), preise(2:end));
        iKombis = [numK * ones(size(restEinkauf,1), 1), restEinkauf];
        kombis = [kombis; iKombis];
    end
else
    % wenn es nur 1 Bauteil gibt, sind die Kombinationen einfach ermittelt
    kombis = (0:floor(guthaben/preise(1)))';
end


Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
General_Griboz
Themenstarter

Forum-Fortgeschrittener

Forum-Fortgeschrittener


Beiträge: 66
Anmeldedatum: 05.04.17
Wohnort: ---
Version: R2016b
     Beitrag Verfasst am: 16.05.2017, 08:09     Titel:
  Antworten mit Zitat      
Moin Harald,

ich habe deinen Code ausprobiert und er funktioniert. Jedoch ist das Problem, dass in jeder Kombination jedes Bauteil max. 1mal auftauchen darf. D.h. ich kann Bauteil1 nicht so oft kaufen bis mein Budget erreicht ist. Und bei dir füllt er immer erstmal mit einem Bauteil so oft auf bis das Budget erreicht ist.

Ich werde mal versuchen, ob man nicht deinen Code daran anpassen kann, das jedes Bauteil das gekauft werden kann, nur einmal vorkommen darf in jeder Kombination.

Aber vllt hast du dazu ja sogar eine Idee.
Private Nachricht senden Benutzer-Profile anzeigen
 
General_Griboz
Themenstarter

Forum-Fortgeschrittener

Forum-Fortgeschrittener


Beiträge: 66
Anmeldedatum: 05.04.17
Wohnort: ---
Version: R2016b
     Beitrag Verfasst am: 16.05.2017, 12:07     Titel:
  Antworten mit Zitat      
Habe bisher leider keine Idee, wie ich deinen Code anpassen kann an meine Bedürfnisse. Ich werde es mal weiter probieren.
Private Nachricht senden Benutzer-Profile anzeigen
 
General_Griboz
Themenstarter

Forum-Fortgeschrittener

Forum-Fortgeschrittener


Beiträge: 66
Anmeldedatum: 05.04.17
Wohnort: ---
Version: R2016b
     Beitrag Verfasst am: 16.05.2017, 15:47     Titel:
  Antworten mit Zitat      
Habe das Problem mit den Kombinationen, in denen Bauteile mehrfach vorkommen über eine neue Funktion gelöst. Ist wohl nicht funktioniert habe, hoffe nur mir schmiert mein Rechner nicht ab, wenn ich mal mehr Bauteile habe und damit die Kombinationen auch in die Höhe gehen.

Das wäre meine 2. Funktion:

Code:
function Liste=kombis_filtern(kombis)
Liste=kombis;
kk=1;
jj=[];
    while kk<=length(Liste(:,1))
        if any(kombis(kk,:)>1)==1
            jj=[jj;kk];
            kk=kk+1;
        else
            kk=kk+1;
        end
    end
    Liste(jj,:)=[];
    Liste(1,:)=[];
end
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 16.05.2017, 17:04     Titel:
  Antworten mit Zitat      
Hallo,

die schnellste Anpassung:
Code:
for numK = 0:min(1, floor(guthaben/preise(1)))

und im else-Teil:
Code:
kombis = (0:min(1,floor(guthaben/preise(1))))';


Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
General_Griboz
Themenstarter

Forum-Fortgeschrittener

Forum-Fortgeschrittener


Beiträge: 66
Anmeldedatum: 05.04.17
Wohnort: ---
Version: R2016b
     Beitrag Verfasst am: 17.05.2017, 08:21     Titel:
  Antworten mit Zitat      
Moin Harald,

das funktioniert. Nun werde ich noch Versuchen, die Kombinationen rauszuschmeißen, wo er immer nur 1 Bauteil reinpackt obwohl, noch Guthaben da sein müsste. So sieht es im Moment aus, wenn man folgende Bauteile nimmt und ein Budget von 500€ benutzt.

1. Bauteil1 100€
2. Bauteil2 200€
3. Bauteil3 300€

Das sind die Kombinationen:
1. 0 Bauteile
2. Bauteil3
3. Bauteil2
4. Bauteil2+Bauteil3
5. Bauteil1
6. Bauteil1+Bauteil3
7. Bauteil1+Bauteil2

Am besten wäre es wenn der Code nur die Kombinationen 4.,6. und 7. ausgibt, denn diese Reizen das Budget am meisten aus.
Private Nachricht senden Benutzer-Profile anzeigen
 
General_Griboz
Themenstarter

Forum-Fortgeschrittener

Forum-Fortgeschrittener


Beiträge: 66
Anmeldedatum: 05.04.17
Wohnort: ---
Version: R2016b
     Beitrag Verfasst am: 17.05.2017, 10:31     Titel:
  Antworten mit Zitat      
Oder eine andere Frage dazu, könnte man diesen Code irgendwie beschleunigen? Denn wenn ich z.B. 100 Bauteile habe, werden es ja ganz bschön viele Kombinationen.
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 17.05.2017, 18:07     Titel:
  Antworten mit Zitat      
Hallo,

wie legst du allgemein fest, welche Kombinationen das Budget ausreichend ausreizen.

Der rekursive Ansatz ermöglicht nicht, das vorab zu filtern. Das kannst du erst im Nachhinein machen. Bitte möglichst von vorneherein alle Informationen liefern. Es ist recht mühsam, wenn man einen Ansatz immer weiter anpassen muss.

Zitat:
Oder eine andere Frage dazu, könnte man diesen Code irgendwie beschleunigen?

Ich wüsste nicht wie. Wenn ich es wüsste, hätte ich von vorneherein die schnellere Version geschickt.

Zitat:
Denn wenn ich z.B. 100 Bauteile habe, werden es ja ganz schön viele Kombinationen.

Man müsste theoretisch annähernd 2^100 = 1.2677e+30 durchtesten. Das ist ziemlich unrealistisch.

Was willst du denn mit all diesen Kombinationen machen?

Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
General_Griboz
Themenstarter

Forum-Fortgeschrittener

Forum-Fortgeschrittener


Beiträge: 66
Anmeldedatum: 05.04.17
Wohnort: ---
Version: R2016b
     Beitrag Verfasst am: 17.05.2017, 18:17     Titel:
  Antworten mit Zitat      
Moin Harald,

es tut mir leid, dass ich am Anfang nicht so konkret geworden bin.

Zitat:
wie legst du allgemein fest, welche Kombinationen das Budget ausreichend ausreizen.


Wenn die Kosten für die Bauteile möglichst nahe an meinem Budget liegen oder sie im besten fall genauso hoch sind wie mein Budget.

Jeder Kombination, die unterhalb meinem Budget oder gleich meinem Budget ist, kann ich hinterher einen gesamtausfall zuordnen, da jedes genommene Bauteil einen Ausfall erzeugt. Und dann können die Kombinationen gefiltert werden, sodass ich alle Kombinationen bekomme, die am dichtesten an meinem maximal tolerierten Ausfall liegen.

Gruß
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen

Gehe zu Seite 1, 2, 3  Weiter

Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.