Greedy-Algorithmen

#1
1547140538181.png
Wir haben uns überlegt, dass wir einfach beide gegebene Mengen also A und R in aufsteigender Reihenfolge sortieren, dann bei i=1 anfangen und dann einfach das produkut ausrechene, und i dann immer um eins iterieren.

Aber so einfach wird das Wahrscheinlich nicht funktionieren oder ?
 

Jan Krüger

Well-Known Member
c-b Team
c-b Experte
#2
Prinzipiell sieht das für mich richtig aus, aber Greedy heißt ganz streng gesehen, dass man mit den höchsten Werten anfängt -- bei aufsteigender Sortierung fängst du mit den niedrigsten an.

Bei Greedy sagst du quasi: ich greife mir zuerst die beiden höchsten Werte, da ich damit ja sicher die größtmögliche Potenz bilden kann. Dann nehme ich die höchsten, die danach noch übrig sind, usw. Du machst im Endeffekt das Gleiche, nur rückwärts... ich würde es umdrehen, dann ist es näher am Greedy-Konzept.
 
Oben