Gegeben eine Liste von n ganzen Zahlen, finde die minimale Subsetsumme größer als X

Question

Gegeben eine unsortierte Menge von ganzen Zahlen in der Form eines Arrays, finde die minimale Subsetsumme größer als oder gleich einer const Integer x.

zB: - Unser Set ist {4 5 8 10 10} und x=15 so die minimale Teilmenge Summe am nächsten x und >=x is {5 10}

ich nur einen naiven Algorithmus denken kann, die alle Untergruppen von Satz listet und überprüft, ob Summe der Teilmenge >=x und Minimum oder nicht, aber es ist ein exponentieller Algorithmus und Auflistung aller Teilmengen erfordert O (2^N). Kann ich dynamische Programmierung verwenden, um sie in polynomieller Zeit zu lösen?

Answer 1

Wenn die Summe aller Ihrer Zahlen S ist, und Ihre Zielnummer X, können Sie die Frage wie diese anders formulieren können: können Sie die maximale Teilmenge der Zahlen wählen, die kleiner oder gleich S-X ist?

Und Sie haben einen Sonderfall der knapsack problem, wo Gewicht und Wert gleich sind.

Das sind schlechte Nachrichten, weil es bedeutet, dass Ihr Problem NP-schwer ist, aber auf der Oberseite können Sie nur die dynamische Programmierlösung des KP verwenden (die immer noch nicht polynomial ist). Oder Sie können eine polynome Approximation des KP ausprobieren, wenn Ihnen das gut genug ist.