Hoechstmoegliche zahl <100 finden

[Snc]

Hallo

Beschaeftige mich erst seit kurzem mit c++ und stehe nun vor einem problem

Der benutzer soll eine beliebige anzahl an int werten eingeben koennen. Zum beispiel 40 50 70 5

Das programm soll dann pruefen welche zusammenstellung dieser werte am naehsten am wert 100 liegt und den uebrig gebliebenen rest auch ausgeben
Beispiel 40 50 5 passen rein-> 95
70 bleibt uebrig

Mein erster gedanke war nach der eingabe der werte mit if anweisungen zu pruefen ob moegliche konstellationen < 100 sind, jedoch wuerde man selbst bei nur 10 positionen bereits x-zeilen an code schreiben muessen um jede moeglichkeit der zusammenstellung durchzupruefen

Gibt es vlt eine function aus der std library oder kann mir jemand einen tipp geben wie man dies eleganter loesen koennte?

[life]

Das ist eine Beispielinstanz des Subset Sum Problems. Im Prinzip musst du also wirklich einfach alle Konstellationen durchprobieren. Das macht man typischerweise aber nicht hard-codiert, direkt im Programmcode, sondern benutzt z.B. einen Backtracking Algorithmus, um die ganzen Konstellationen dynamisch aufzählen zu lassen.

[wxSkip]

Was mir jetzt in den Sinn käme, wäre eine Schleife mit std::next_permutation() und einer weiteren Schleife, die so viele Zahlen des vectors summiert, bis 100 überschritten wird und den Wert davor mit dem bisherigen Maximalwert vergleicht.

[seldon]

Sollen negative Eingabewerte erlaubt sein? Sonst geht das nämlich bedeutend einfacher und schneller.

[fraaeaeger]

kann man nicht einfach der größe nach sortieren, dann die größtmögliche zahl hinzufügen, gucken ob die nächste noch passt, wenn ja hinzufügen, sonst ab zur nächsten. dann müßte doch am ende die beste menge drinn sein.

[SideWinder]

seldon schrieb:

Sollen negative Eingabewerte erlaubt sein? Sonst geht das nämlich bedeutend einfacher und schneller.

Einfacher als mit Backtracking? Kann ich mir nicht vorstellen. Negative Eingabewerte verhindern ja quasi Backtracking und zwingen dir auf alle Kombinationen zu nutzen. Da kein genauer Wert sondern "< 100" gesucht ist, reicht es bei negativen Werten wohl auch einfach alle negativen Werte zu den 100 dazuzuzählen und dann wieder normal mit nur-positiv zu arbeiten?

MfG SideWinder

[SideWinder]

fraaeaeger schrieb:

kann man nicht einfach der größe nach sortieren, dann die größtmögliche zahl hinzufügen, gucken ob die nächste noch passt, wenn ja hinzufügen, sonst ab zur nächsten. dann müßte doch am ende die beste menge drinn sein.

Nein, dem ist nicht so.

Beispiel:

Bedingung < 11
Zahlen: 9, 5, 5

Max: 5, 5
Deine Methode: 9

MfG SideWinder

[berniebutt]

seldon schrieb:

Sollen negative Eingabewerte erlaubt sein? Sonst geht das nämlich bedeutend einfacher und schneller.

Ich denke, negative Werte nein. Wie sieht denn dein einfacher und schneller Algorithmus aus, wenn die Anzahl der möglichen Kombinationen effektiv eingegrenzt werden soll? Zeig her!!!
Bei bis zu 10 Werten ist alles noch kein grosses Problem. Bei 100 Werten oder mehr zeigt sich, was der Algorithmus taugt.

Vorher einen Sort anschmeissen, kann ich mir gut vorstellen.

[drakon]

SideWinder schrieb:

fraaeaeger schrieb:

kann man nicht einfach der größe nach sortieren, dann die größtmögliche zahl hinzufügen, gucken ob die nächste noch passt, wenn ja hinzufügen, sonst ab zur nächsten. dann müßte doch am ende die beste menge drinn sein.

Nein, dem ist nicht so.

Oder wie unser Prof. zu sagen pflegte: Das kann so beliebig schlecht werden. ^^

[life]

drakon schrieb:

SideWinder schrieb:

fraaeaeger schrieb:

kann man nicht einfach der größe nach sortieren, dann die größtmögliche zahl hinzufügen, gucken ob die nächste noch passt, wenn ja hinzufügen, sonst ab zur nächsten. dann müßte doch am ende die beste menge drinn sein.

Nein, dem ist nicht so.

Oder wie unser Prof. zu sagen pflegte: Das kann so beliebig schlecht werden. ^^

Das hätte euer Prof. vermutlich nicht gesagt. Rein intuitiv sollte es sowas wie "mindestens halb soviel wie das Optimum" sein.

[drakon]

Jup. In dem Fall schon. Er hats bei Knappsack gesagt.
IIRC hat er das sogar bewiesen für ein ähnliches Problem, dass es dort nur halb so schlecht wird wie das Optimum.

[seldon]

Wenn negative Eingabewerte verboten sind, muss ich mir zu jedem Zeitpunkt höchstens 100 (bzw. so viele, wie halt die Obergrenze umfasst) Teilsummen merken - unter Null geht nicht, und was über 100 liegt, ist für die weitere Berechnung nicht mehr relevant. Die Laufzeitkomplexität sinkt damit auf O(m * n), wobei m die Obergrenze und n die Anzahl der eingegebenen Zahlen ist.

Implementieren könnte man das beispielsweise so:

#include <iostream>
#include <list>
#include <vector>

class subsetsum {
public:
  subsetsum() : value_(0), parent_(0) { }

  subsetsum(unsigned new_value, subsetsum const *parent)
    : value_(parent->value() + new_value),
      parent_(parent) 
  { }

  unsigned  const  value () const { return  value_; }
  subsetsum const *parent() const { return parent_; }

private:
  unsigned         value_;
  subsetsum const *parent_;
};

bool operator<(subsetsum const &lhs, subsetsum const &rhs) { return lhs.value() < rhs.value(); }

typedef std::list<subsetsum> container_t;

int main() {
  unsigned x;
  unsigned const treshold = 100;

  std::vector<bool> already_found(treshold + 1, false);
  container_t valid_sums;

  valid_sums.push_back(subsetsum());
  already_found[0] = true;

  while(std::cin >> x && !already_found[treshold]) {
    container_t new_sums;

    for(container_t::const_iterator iter = valid_sums.begin(); iter != valid_sums.end(); ++iter) {
      unsigned new_sum = iter->value() + x;

      if(!already_found[new_sum] && new_sum <= treshold) {
        new_sums.push_back(subsetsum(x, &*iter));
        already_found[new_sum] = true;
      }
    }

    valid_sums.splice(valid_sums.end(), new_sums);
  }

  valid_sums.sort();

  std::cout << valid_sums.back().value() << '\n';

  for(subsetsum const *p = &valid_sums.back(); p->value(); p = p->parent()) {
    std::cout << p->value() - p->parent()->value() << ' ';
  }
  std::cout << std::endl;
}

Wobei da mit Sicherheit noch Luft für Performanceoptimierung ist.

[life]

Das nennt sich dann Pseudopolynomiell (wächst immer noch exponentiell mit der Eingabegröße).

Siehe auch: http://de.wikipedia.org/wiki/Rucksackproblem#L.C3.B6sung_mittels_dynamischer_Programmierung

[life]

drakon schrieb:

IIRC hat er das sogar bewiesen für ein ähnliches Problem, dass es dort nur halb so schlecht wird wie das Optimum.

Der Beweis ist nicht schwierig. Mach einfach einen Widerspruchsbeweis:

Angenommen unser Greedy-Algorithmus liefert eine Lösung/Teilmenge L dessen Summe der Elemente weniger als die Hälfte der Summe der Elemente der optimalen Teilmenge beträgt. Dann gibt es offenbar ein Element e in der optimalen Teilmenge, das nicht nicht in Greedy Lösung vorkommt. Der Wert dieses Elementes e muss aber weniger als die Hälfte der Summe der Elemente der optimalen Lösungen betragen, denn ansonsten hätte der greedy Algorithmus dieses (oder ein noch höherwertigeres) Element genommen und die Summe der Elemente der Greedy-Lösung wäre nicht weniger als die Hälfte. Entsprechend ist der Wert von e auch weniger als die Hälfte der maximalen Schranke (100 in diesem Fall) und man kann die Greedy-Lösung L (dessen Summe der Elemente ja auch weniger als die Hälfte der maximalen Schranke beträgt) um e erweitern ohne die Schranke zu überschreiten. Dies steht aber im Widerspruch zur Definition des Greedy-Algorithmus, der solange Elemente zu L hinzufügt, bis keines mehr hineinpasst ohne die maximale Schranke zu überschreiten.

[drakon]

Ich hatte die allgemeine Herleitung der Güte von FPTAS des Knapsack Problems im Kopf, die relativ schwierig war.

[berniebutt]

@seldon und andere

hier eine einfache sortierte positive Eingabefolge zum Testen:
1 2 3 4 4 5 90 92

1 2 3 4 4 4 90 92 --> 99
1 2 3 4 4 5 90 92 --> 99
1 2 3 4 4 5 90 92 --> 99
1 2 3 4 4 5 90 92 --> 99

Es kann also mehrfache Lösungen geben. Wie soll man da mit Teilmengen und dem Ausschluss einzelner Werte die Lösung finden?

Ist jetzt aber ein rein mathematisches Thema, nicht unbedingt C++