[php] optimale zusammenstellung

A

ActionScripter

Scripter auf Abruf
ID: 141403
L
17 Oktober 2006
484
39
hallo,

ich steh grad mal wieder auf dem schlauch. ich will ein kleines progrämmchen schreiben, was mir beim briefmarkenkleben hilft. ich habe verschiedene werte:

PHP: 
$marken	= array( 5, 10, 20, 45, 55, 90, 100, 145, 180, 200, 260, 390 );

nun möchte ich eine kombination finden, mit der möglichst wenig marken verklebt werden sollen. wenn ich z.b. 4.40€ benötige, dann spuckt mir mein derzeitiges script (einfach ne schleife, die nach der grösse sortiert) folgendes aus:

1x 3.90€
1x 0.45€
1x 0.05€

das ist richtig, macht aber mehr sinn, wenn ich 1x 2.60€ und 1x 1.80€ erhalte.

bin inzwischen so lange aus der programmierung raus, dass mir die ideen dazu fehlen. vielleicht kann mir jemand auf die sprünge helfen, wie man das angeht...

danke
 
Puh.. kugg doch mal auf den Seiten des BWINF. Da war doch zumindest kürzlich ein Problem mit welchen Münzen man am schlauesten bezahlt, um möglichst wenig Münzen Rückgeld zu bekommmen (oder ähnlich). Und vielleicht war dein Problem so oder so ähnlich früher schon mal dran. Oder du bekommst dort vielleicht aus den Lösungen Ansätze für deine eigene. Ansonsten kann ich da leider auch nicht helfen, wollte den Tipp aber mal anbringen. :)
 
EDIT:

Sorry hatte ich falsch verstanden, sehe jetzt oben dein Problem.

Naja überarbeite doch mal die Logik deiner markenauswahl, um möglichst wenig Marken zu verbrauchen brauchst du ja die größte Mögliche also solltest du das Array von Oben nach unten abarbeiten und dann die erste Marke dessen Wert gleich oder unter dem benötigten Wert liegt auswählen solange bis der Wert erreicht ist.

PHP: 
$marken=array(390,260, usw....);
$rest=$porto;
 
while ($rest>0) {
 
   foreach ($marken as $marke) {
      if ($marke<=$rest) {
         echo"Klebe $marke ";
         $rest=$rest-$marke;
         break;
      }
   }
 
}
 
Zuletzt bearbeitet:
Ein Greedy-Algorithmus, was du wahrscheinlich probiert hast, wird hier nicht funktionieren, da die Matroideigenschaft nicht erfüllt ist (Klugscheiß)

Damit kannst du in diesem Fall nur ein lokales Maximum rauskriegen. Weiß nicht obs überhaupt nen effizienten Algorithmus dafür gibt. Evtl. hilft dynamisches Programmieren, aber ich hab leider grad keine Zeit mir mehr gedanken darüber zu machen.
 
@happymaster: wo find ich da lösungen? ich seh nur die aufgabenstellungen...

@teilzeitelf: habs natürlich absteigend gemacht. wollt jetzt nur nicht noch das script reinstellen, weil ist zu billig *g*

@ttplayer: öhm ... aja ... sorry, aber mit deiner antwort kann ich rein gar nix anfangen. was verstehst du unter "dynamischem programmieren"??
 
Ohne jetzt vernünftigen Code anbietne zu können einfach mal eine Überlegung zu einem Lösungsansatz.

Zunächst:
- Die größte Marke nehmen und prüfen wie oft die ins Gesamtporto paßt und die schonmal Kleben.

Beim Rest wie folgt verfahren:

- Markenarray von oben nach unten durchlaufen, wenn zufällig der Restwert einer Marke entspricht natürlich die Kleben wenn nicht prüfen ob bei Wahl dieser Marke der zukünftige Rest Betrag einer Marke entsprechen würde. Wenn ja -> Die Marke Kleben, wenn nicht zunächst das Array bis zum Ende durchlaufen.

Wurde keine Marke gefunden die direkt paßt und auch keine Marke gefunden die bei der nächsten Marke zum Ziel führt einfach die mit dem höchst möglichstem Wert auswählen und verkleben. Mit dem Restwert das Spielchen dann solange vortsetzen bis der Betrag erreicht ist.

EDIT:

Hmm nein bringt auch nciht wirklch weiter.... ARGH... jetzt denke ich den Rest des Tages an Briefmarken
 
Musst mal in der 1. Runde unter Lösungshinweise schauen, da steht das.

Dort ist es auch gut beschrieben :)
 
Ich würde das ganz primtiv per Brutforce lösen... bei diesen Werte ist das ohne weiteres möglich. Das ganze mal ein wenig näher erläutert... ich würde mir die 3-5 größten werte nehmen die unter oder gleich (...) dem Porto sind. Für jeden dieser Werte würde ich jetzt von oben bis unten durchgehen und solange versuchen bis ich auf das Proto komme. (der Algorithmus ist ja schon da) Das ganze wird einfach zwischen gespeichert und für die restlichen 3-5 Startwerte auch gemacht. Am ende schaust du einfach welcher Startwert die wenigsten Werte gebraucht hat. Ist zwar nicht optimal, aber vielleicht ein brauchbarer Ansatz für diesen Wertebereich.
 
@TT
Öhm ok, ich habe mir den gerade auf Wikipedia angeschaut und kein Wort verstanden, aber gut zu wissen :)

ZeroCCC schrieb:
Ich würde das ganz primtiv per Brutforce lösen...
Zum Vergrößern anklicken....

Hm da könnte man fast hergehen und eine Tabelle aufstellen die alle möglichen Porto Kosten enthalten und die dazugehörigen Briefmarken die zu kleben sind aber ads würde der Sache den Spaß nehmen ^^. (Auch wenn es 10 mal schneller gehen würde *g*)
 
Ohne jetzt länger drüber nachzudenken, würde ich vermuten, dass das ein NP-Vollständiges Problem ist, für das es aber vermutlich einen pseudopolynomiellen Algorithmus geben dürfte.

D.h. letzendlich, dass es keinen tollen Algorithmus gibt, sondern man im Prinzip alle Möglichkeiten ausprobieren muss (wobei natürlich manche direkt wegfallen).

Ich würde bei der Marke anfangen, die am größten von denen ist, die <= dem Zielwert sind. Sobald du dann eine Kombination gefunden hast, speicherst du die Anzahl Marken (x) und testest alle anderen Kombinationen, brichst aber ab, sobald du mit (x - 1) Marken die Bedingung noch nicht erfüllt hast.
 
also vielen dank für die menge an ansätzen. hab wiedermal nen haufen gelesen und gelernt und trotzdem dann den weg des geringsten widerstandes gescriptet *g*

das ergebnis ist letzlich ein script, was (wenn ich das richtig verstanden habe) greedy und bruteforce vereint:

PHP: 
$marken	= array( 390, 260, 200, 180, 145, 100, 90, 55, 45, 20, 10, 5 );
function getBestChoice( $zahl ) {
  global $marken;
  if( $zahl % $marken[count($marken)-1] > 0 )  return false;
  $arr    = array_fill_keys( $marken, 0 );
  $res    = false;
  $max    = floor( $zahl / $marken[count($marken)-1] );
  for( $pnt=0; $pnt<count($marken); $pnt++ ) {
    if( $marken[$pnt]>$zahl ) continue;
    $tmp  = $arr;
    if( fillArray( $tmp, $pnt, $zahl, $max ) ) $res = $tmp;
  }
  return $res;
}

function fillArray( &$arr, $pnt, $zahl, &$max ) {
  global $marken;
  $cnt  = 0;
  while( $pnt<count($marken) ) {
    if( $marken[$pnt]>$zahl ) {
      $pnt++;
      continue;
    }
    $arr[$marken[$pnt]]++;
    $zahl -= $marken[$pnt];
    if( ++$cnt>$max ) return false;
  }
  $max  = $cnt;
  return true;
}

ist sicherlich nicht die beste methode, aber da die beträge ja überschaubar sind gehts recht zuverlässig :)


danke für die anregungen ...
 
Johnson, erinnerst du dich an unsere Verzweiflung mit den Laufzeiten :LOL:

tooooooooooooobi, schön das du wieder da bist :D
Lösungshinweise 25. BWINF Runde 1, Aufgabe 1: Närrische Wirtschaft ;)

das Problem ist als Rucksackproblem oder auch Subset-Sum-Porblem bekannt und daher nicht so trivial zu lösen
 
ach leute, so wirklich bin ich nicht wieder da. eher ein schatten meiner selbst. aber ich lebe noch (oder wieder) und versuch mal wieder von ganz unten nach ganz oben zu kommen. das ist jetzt der 5. neuanfang mit rekordminus und so langsam hab ich echt keinen bock mehr. aber wenigstens hat dieser versuch nicht mehr viel mit programmierung zu tun. mach nur noch ein paar sachen für mich und "sichere" aufträge fürs kleingeld.

aber keine bange. ihr seid mich erst los, wenn der nächste intelligenz-verweigerer sich ein auto kauft. nochmal bremse ich nicht ;(
 
Du musst dich einloggen oder registrieren, um hier zu antworten.

Ähnliche Themen

chatgptdeutsch
    • Like
Effektive Nutzung von ChatGPT Deutsch Kostenlos: Strategien für optimale Ergebnisse
Antworten
1
Aufrufe
8K
ice_crusher
I
Zurück
Oben