我正在尝试针对划分问题“NP Hard”实现 dfs 算法，将集合 S 划分为两个子集 S1 和 S2，以便 S1 的元素之和与 S2 的元素之和之间的差 D是最小的
解决方案示例：
S1= 2 7 22 51 16 2 Σ S1i = 100
S2= 13 6 57 24 Σ S2j = 100 D = | Σ S1i - Σ S2j | = | 100 - 100 | = 0
这是我使用 java 的解决方案，但是有一个问题，代码没有显示最佳解决方案。任何人都可以帮忙吗？
package partition_problem;
import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;
public class partition {
private ArrayList<Integer> subset1;
private ArrayList<Integer> subset2;
public partition (ArrayList<Integer> subset1, ArrayList<Integer> subset2) {
this.subset1 = subset1;
this.subset2 = subset2;
}
public ArrayList<Integer> getSubset1() {
return subset1;
}
public ArrayList<Integer> getSubset2() {
return subset2;
}
public void setS1(ArrayList<Integer> s1) {
subset1 = s1;
}
public void setS2(ArrayList<Integer> s2) {
subset2 = s2;
}
// METHODE RETOURNE UNE INSTANCE AU PROBLEME
public static ArrayList<Integer> instance_pb() {
try (Scanner scanner = new Scanner(System.in)) {
Random random = new Random();
System.out.print("Entrez le nombre d'éléments dans l'ensemble : ");
int n = scanner.nextInt();
ArrayList<Integer> S = new ArrayList<>();
System.out.print("L'ensemble S initiale est : ");
for (int i = 0; i < n; i++) {
int element = random.nextInt(100); // génère un entier aléatoire entre 0 et 99
S.add(element);
System.out.print(element + " ");
}
return S;
}
}
public static partition generateRandomSolution(ArrayList<Integer> set) {
// Créer deux sous-ensembles vides
ArrayList<Integer> subset1 = new ArrayList<>();
ArrayList<Integer> subset2 = new ArrayList<>();
// Parcourir le vecteur initial et ajouter chaque élément à l'un ou l'autre sous-ensemble de manière aléatoire
Random random = new Random();
for (int i = 0; i < set.size(); i++) {
if (random.nextBoolean()) {
subset1.add(set.get(i));
} else {
subset2.add(set.get(i));
}
}
System.out.println("S1");
for (int i = 0; i < subset1.size(); i++) {
System.out.print(subset1.get(i) + " ");
}
System.out.print("\n");
System.out.println("S2");
for (int i = 0; i < subset2.size(); i++) {
System.out.print(subset2.get(i) + " ");
}
partition solution = new partition(subset1, subset2);
return solution;
}
//Vérification de la validité de la solution
public static boolean isSolutionValid(ArrayList<Integer> originalSet, partition solution) {
ArrayList<Integer> subset1 = solution.getSubset1();
ArrayList<Integer> subset2 = solution.getSubset2();
// Vérifier que tous les éléments de l'ensemble initial sont dans les 2 sous-ensembles
ArrayList<Integer> allSubsets = new ArrayList<>(subset1);
allSubsets.addAll(subset2);
if (!originalSet.containsAll(allSubsets)) {
return false;
}
// Vérifier que chaque élément du premier sous-ensemble n'est pas dans le deuxième sous-ensemble, et vice versa
for (Integer element : subset1) {
if (subset2.contains(element)) {
return false;
}
}
for (Integer element : subset2) {
if (subset1.contains(element)) {
return false;
}
}
return true;
}
/*Evaluate the solution
l'évaluation consiste a comparer la somme des deux tableaus
si la différence <=5 c'est un bonne solution si 5<D<30 alors on a une solution moyen si D>30 alors la solution est mauvaise */
public static int evaluate(partition solution) {
int sum1 = 0, sum2 = 0;
for (int i = 0; i < solution.getSubset1().size(); i++) {
sum1 += solution.getSubset1().get(i);
}
for (int i = 0; i < solution.getSubset2().size(); i++) {
sum2 += solution.getSubset2().get(i);
}
int D= Math.abs(sum1 - sum2);
return D;
}
public static void main(String[] args) {
ArrayList<Integer> set = partition.instance_pb();
/*partition solution = partition.generateRandomSolution(set);
boolean isValid = partition.isSolutionValid(set, solution);
partition.evaluate(solution);*/
System.out.println("\n recherche en cours de la meilleure solution...");
partition solution = DFS.DFS_search(set);
System.out.println("sous ensemble 1 est: " +solution.subset1);
System.out.println("sous ensemble 1 est: " +solution.subset2);
}
package partition_problem;
import java.util.ArrayList;
import java.util.Stack;
public class DFS {
public static partition DFS_search (ArrayList<Integer> set) {
Stack<partition> open = new Stack<>();
ArrayList<partition> closed = new ArrayList<>();
partition bestSolution = null;
partition root = new partition(new ArrayList<Integer>(), set);
open.push(root);
while (!open.isEmpty()) {
partition node = open.pop();
closed.add(node);
if (node.getSubset2().isEmpty()) { // État final trouvé
if (bestSolution == null || partition.evaluate(node) > partition.evaluate(bestSolution)) {
bestSolution = node;
}
} else {
ArrayList<partition> successors = generateSuccessors(node,set);
for (partition successor : successors) {
if (!closed.contains(successor)) {
open.push(successor);
}
}
}
}
System.out.println("\nla différence entre la somme des 2 sous ensembles est : " +partition.evaluate(bestSolution));
return bestSolution;
}
public static ArrayList<partition> generateSuccessors(partition node,ArrayList<Integer> OriginalSet ) {
ArrayList<partition> successors = new ArrayList<>();
ArrayList<Integer> set1 = node.getSubset1();
ArrayList<Integer> set2 = node.getSubset2();
if (!set1.isEmpty()) {
int lastElement = set1.get(set1.size() - 1);
ArrayList<Integer> newSet1 = new ArrayList<>(set1);
newSet1.remove(newSet1.size() - 1);
ArrayList<Integer> newSet2 = new ArrayList<>(set2);
newSet2.add(lastElement);
partition successor = new partition(newSet1, newSet2);
if (partition.isSolutionValid(OriginalSet, successor)) {
successors.add(successor);
}
}
if (!set2.isEmpty()) {
int lastElement = set2.get(set2.size() - 1);
ArrayList<Integer> newSet1 = new ArrayList<>(set1);
newSet1.add(lastElement);
ArrayList<Integer> newSet2 = new ArrayList<>(set2);
newSet2.remove(newSet2.size() - 1);
partition successor = new partition(newSet1, newSet2);
if (partition.isSolutionValid(OriginalSet, successor)) {
successors.add(successor);
}
}
return successors;
}
}