Sie können alle Teilmengen mit einer Branch-and-bound-Technik generieren: Sie können alle Teilmengen inkrementell generieren (indem Sie eine Obermenge von bereits bestimmten Teilmengen generieren), indem Sie diese Verzweigung "nicht untersuchen" der Baum, wenn die Wurzel die Beschränkung nicht erfüllt ".
Wenn Sie bezüglich der Beschränkung generisch sein wollen, denke ich, dass dies die beste Strategie ist.
Achten Sie darauf, den Code korrekt zu schreiben, der die Subsets erzeugt, sonst erzeugen Sie viele Zeit die gleichen Subsets: um Memoization zu vermeiden, die aufgrund von Map-Lookups zeitraubend sein kann und Speicher Overhead einführt die Teilmengen in dieser Weise erzeugen:
GetAllSubsets(List objects) {
List generated = {};
GetAllSubsets(generated, [], objects);
return generated;
}
GetAllSubsets(List subsetGenerated, List objectFixed, List objectsToFix) {
GetAllSubsets(subsetGenerated, objectFixed, objectsToFix.sublist(1, objectsToFix.length());
if (satisfy(toCheck = objectsFixed.add(objectsToFix.get(0)))) {
subsetGenerated.add(toCheck);
GetAllSubsets(subsetGenerated, toCheck, objectsToFix.sublist(1, objectsToFix.length());
}
}
in der Tat, die Teilmengen von dem ersten Aufruf von GetAllSubsets hinzugefügt nicht das erste Element des objectsToFix aufweisen, wobei die Teilmengen durch den zweiten Anruf (wenn die Bedingung hinzugefügt pruning ist nicht verletzt) haben dieses Element, so ist der Schnittpunkt der beiden Gruppen von Untergruppen erzeugt leer.
Es macht keinen Sinn, über alle Mengen zu iterieren; Wenn die Summe von (x, y) größer als 100 ist, muss keine verbleibende Teilmenge mit x, y überprüft werden! (Zum Beispiel: (40,79,50) hat eine Summe von mehr als 100, es gibt also keine Notwendigkeit zu überprüfen (40,79,50,1), (40,79,50,66,1) etc ... – ooboo
Aber das ist nur ein Beispiel der möglichen Bedingungen.Was ist, wenn die Bedingung ist, dass die Summe weniger als 5050 ist (was die Summe von 1 bis 100 ist)? Dann werden * alle * Untergruppen die Bedingung erfüllen. –
Aber die Tatsache, dass Im schlimmsten Fall erhalten Sie eine O (2^n) Zeit Komplexität sollte uns nicht daran hindern, eine gute Heuristik zu suchen, um das Problem zu lösen – akappa