Алгоритм поиска наилучшей комбинации списка, если заданы множества

Question

Я ищу алгоритм, чтобы найти лучшую комбинацию (самый большой вес) из списка наборов.Например, допустим, у нас есть пункты «А», «В» и «С», и мы получили 4 А, 2 В и 3 С.Возможны следующие комбинации:

{A,B,C},{A,B,C},{A,C},{A}
{A,B},{A,B,C},{A,C},{A,C}

Тогда веса основаны на количестве предметов в наборе, например:

1 предмет: 5

2 предмета:15

3 предмета: 20

Таким образом, в этом случае первая комбинация будет иметь вес 20 + 20 + 15 + 5 = 60, а вторая - 15 + 20 + 15 +.15 = 65.Жадный алгоритм не сработает в этом случае, потому что есть случаи, когда поиск наибольшего количества предметов не возвращает наилучшую комбинацию.

Есть идеи?

Answer 1

Я решил это с помощью рекурсии.

Эти переменные определяют проблему (статические переменные):

private static boolean[] BEST_SOLUTION_SO_FAR = null;
private static int BEST_WEIGHT_SO_FAR = 0;

private static String[][] POSSIBLE_SETS =  {{"A","B","C"},{"A","B","C"},{"A","C"},{"A"},{"A","B"},{"A","B","C"},{"A","C"},{"A","C"}};

private static Map<String, Integer> MAX_OF_EACH_ITEM = new HashMap<>();
static {
    MAX_OF_EACH_ITEM.put("A", 4);
    MAX_OF_EACH_ITEM.put("B", 2);
    MAX_OF_EACH_ITEM.put("C", 3);
}

Это основной метод (который устанавливает все для начала рекурсии):

public static void main(String[] args) {
    BEST_WEIGHT_SO_FAR = 0;
    BEST_SOLUTION_SO_FAR = null;

    // start the recursion
    buildSolution(new boolean[POSSIBLE_SETS.length], new HashMap<>());

    // print solution
    System.out.println("BEST SOLUTION : ");
    for (int i = 0; i < POSSIBLE_SETS.length; i++) {
        if(BEST_SOLUTION_SO_FAR[i]){
            System.out.println(Arrays.toString(POSSIBLE_SETS[i]));
        }
    }
}

И это рекурсивный метод:

private static void buildSolution(boolean[] isSelected, Map<String, Integer> itemsUsed){
    boolean canBeExpanded = false;
    for (int i = 0; i < isSelected.length; i++) {
        // check whether another set can be added
        if(!isSelected[i]){

            // calculate new numbers of items used
            Map<String, Integer> itemsUsedB = new HashMap<>(itemsUsed);
            for (int j = 0; j < POSSIBLE_SETS[i].length; j++) {
                String key = POSSIBLE_SETS[i][j];
                if(itemsUsedB.containsKey(key))
                    itemsUsedB.put(key, itemsUsedB.get(key) + 1);
                else
                    itemsUsedB.put(key, 1);
            }

            // check whether this is possible
            boolean isPossible = true;
            for(String key : MAX_OF_EACH_ITEM.keySet()){
                if(itemsUsedB.containsKey(key) && itemsUsedB.get(key) > MAX_OF_EACH_ITEM.get(key)){
                    isPossible = false;
                    break;
                }
            }

            // if not possible attempt next
            if(!isPossible)
                continue;

            // mark this solution as expandable
            canBeExpanded = true;

            // mark as selected
            isSelected[i] = true;

            // recurse
            buildSolution(isSelected, itemsUsedB);

            // undo mark
            isSelected[i] = false;
        }
    }
    // a solution that can no longer be expanded was found
    if(!canBeExpanded){
        int w = 0;
        int[] setSizeWeight = {0,5,15,20};
        for (int i = 0; i < isSelected.length; i++) {
            w += isSelected[i] ? setSizeWeight[POSSIBLE_SETS[i].length] : 0;
        }
        if(w > BEST_WEIGHT_SO_FAR){
            BEST_WEIGHT_SO_FAR = w;
            BEST_SOLUTION_SO_FAR = Arrays.copyOf(isSelected, isSelected.length);
        }
    }
}

Вывод:

ЛУЧШЕЕ РЕШЕНИЕ
[A, B, C]
[A, C]
[A, B]
[A, C]

, который имеет вес 65.