Рюкзак с КОНКРЕТНЫМ КОЛИЧЕСТВОМ предметов из разных групп

Полный код также в: https://github.com/pabloroldan98/knapsack-football-formations

Пояснение после кода.

Этот код предназначен для примера, когда у вас есть Fantasy League с playersDB, где у каждого игрока есть цена (вес), очки (значение) и позиция (группа); есть список possible_formations (групповых вариаций); и budget (W) вы не можете перейти.

Полный код:

• main.py:

    from group_knapsack import best_full_teams
  
    playersDB = [
        Player(name = "Keylor Navas", price=16, points=7.5, position = "GK"),
        Player(name = "Laporte", price=23, points=7.2, position = "DEF"),
        Player(name = "Modric", price=22, points=7.3, position = "MID"),
        Player(name = "Messi", price=51, points=8.2, position = "ATT"),
        ...
    ]
  
    possible_formations = [
        [3, 4, 3],
        [3, 5, 2],
        [4, 3, 3],
        [4, 4, 2],
        [4, 5, 1],
        [5, 3, 2],
        [5, 4, 1],
    ]
  
    budget = 300
  
  
    best_full_teams(playersDB, possible_formations, budget)
  

• group_knapsack.py:

    import itertools
  
    from MCKP import knapsack_multichoice_onepick
  
  
    def best_full_teams(players_list, formations, budget):
        formation_score_players = []
  
        for formation in formations:
            players_points, players_prices, players_comb_indexes = players_preproc(
                players_list, formation)
  
            score, comb_result_indexes = knapsack_multichoice_onepick(
                players_prices, players_points, budget)
  
            result_indexes = []
            for comb_index in comb_result_indexes:
                for winning_i in players_comb_indexes[comb_index[0]][comb_index[1]]:
                    result_indexes.append(winning_i)
  
            result_players = []
            for res_index in result_indexes:
                result_players.append(players_list[res_index])
  
            formation_score_players.append((formation, score, result_players))
  
            print("With formation " + str(formation) + ": " + str(score))
            for best_player in result_players:
                print(best_player)
            print()
            print()
  
        formation_score_players_by_score = sorted(formation_score_players,
                                                  key=lambda tup: tup[1],
                                                  reverse=True)
        for final_formation_score in formation_score_players_by_score:
            print((final_formation_score[0], final_formation_score[1]))
  
        return formation_score_players
  
  
    def players_preproc(players_list, formation):
        max_gk = 1
        max_def = formation[0]
        max_mid = formation[1]
        max_att = formation[2]
  
        gk_values, gk_weights, gk_indexes = generate_group(players_list, "GK")
        gk_comb_values, gk_comb_weights, gk_comb_indexes = group_preproc(gk_values,
                                                                         gk_weights,
                                                                         gk_indexes,
                                                                         max_gk)
  
        def_values, def_weights, def_indexes = generate_group(players_list, "DEF")
        def_comb_values, def_comb_weights, def_comb_indexes = group_preproc(
            def_values, def_weights, def_indexes, max_def)
  
        mid_values, mid_weights, mid_indexes = generate_group(players_list, "MID")
        mid_comb_values, mid_comb_weights, mid_comb_indexes = group_preproc(
            mid_values, mid_weights, mid_indexes, max_mid)
  
        att_values, att_weights, att_indexes = generate_group(players_list, "ATT")
        att_comb_values, att_comb_weights, att_comb_indexes = group_preproc(
            att_values, att_weights, att_indexes, max_att)
  
        result_comb_values = [gk_comb_values, def_comb_values, mid_comb_values,
                              att_comb_values]
        result_comb_weights = [gk_comb_weights, def_comb_weights, mid_comb_weights,
                               att_comb_weights]
        result_comb_indexes = [gk_comb_indexes, def_comb_indexes, mid_comb_indexes,
                               att_comb_indexes]
  
        return result_comb_values, result_comb_weights, result_comb_indexes
  
  
    def generate_group(full_list, group):
        group_values = []
        group_weights = []
        group_indexes = []
        for i, item in enumerate(full_list):
            if item.position == group:
                group_values.append(item.points)
                group_weights.append(item.price)
                group_indexes.append(i)
        return group_values, group_weights, group_indexes
  
  
    def group_preproc(group_values, group_weights, initial_indexes, r):
        comb_values = list(itertools.combinations(group_values, r))
        comb_weights = list(itertools.combinations(group_weights, r))
        comb_indexes = list(itertools.combinations(initial_indexes, r))
  
        group_comb_values = []
        for value_combinations in comb_values:
            values_added = sum(list(value_combinations))
            group_comb_values.append(values_added)
  
        group_comb_weights = []
        for weight_combinations in comb_weights:
            weights_added = sum(list(weight_combinations))
            group_comb_weights.append(weights_added)
  
        return group_comb_values, group_comb_weights, comb_indexes
  

• MCKP.py:

    import copy
  
  
    def knapsack_multichoice_onepick(weights, values, max_weight):
        if len(weights) == 0:
            return 0
  
        last_array = [-1 for _ in range(max_weight + 1)]
        last_path = [[] for _ in range(max_weight + 1)]
        for i in range(len(weights[0])):
            if weights[0][i] < max_weight:
                if last_array[weights[0][i]] < values[0][i]:
                    last_array[weights[0][i]] = values[0][i]
                    last_path[weights[0][i]] = [(0, i)]
  
        for i in range(1, len(weights)):
            current_array = [-1 for _ in range(max_weight + 1)]
            current_path = [[] for _ in range(max_weight + 1)]
            for j in range(len(weights[i])):
                for k in range(weights[i][j], max_weight + 1):
                    if last_array[k - weights[i][j]] > 0:
                        if current_array[k] < last_array[k - weights[i][j]] + \
                                values[i][j]:
                            current_array[k] = last_array[k - weights[i][j]] + \
                                               values[i][j]
                            current_path[k] = copy.deepcopy(
                                last_path[k - weights[i][j]])
                            current_path[k].append((i, j))
            last_array = current_array
            last_path = current_path
  
        solution, index_path = get_onepick_solution(last_array, last_path)
  
        return solution, index_path
  
  
    def get_onepick_solution(scores, paths):
        scores_paths = list(zip(scores, paths))
        scores_paths_by_score = sorted(scores_paths, key=lambda tup: tup[0],
                                       reverse=True)
  
        return scores_paths_by_score[0][0], scores_paths_by_score[0][1]
  

• player.py:

    class Player:
        def __init__(
                self,
                name: str,
                price: float,
                points: float,
                position: str
        ):
            self.name = name
            self.price = price
            self.points = points
            self.position = position
  
        def __str__(self):
            return f"({self.name}, {self.price}, {self.points}, {self.position})"
  
        @property
        def position(self):
            return self._position
  
        @position.setter
        def position(self, pos):
            if pos not in ["GK", "DEF", "MID", "ATT"]:
                raise ValueError("Sorry, that's not a valid position")
            self._position = pos
  
        def get_group(self):
            if self.position == "GK":
                group = 0
            elif self.position == "DEF":
                group = 1
            elif self.position == "MID":
                group = 2
            else:
                group = 3
            return group
  

Объяснение:

Итак, мне удалось найти решение, переводящее то, что было здесь: Решение задачи о рюкзаке с множественным выбором с C++ на Python. Мое решение также дает путь, который привел вас к этому решению. Он использует динамическое программирование и работает очень быстро.

Входные данные вместо groups[i] имеют веса и значения в виде списка списков, где каждый список внутри представляет значения каждой группы:

• weights[i] = [weights_group_0, weights_group_1, ...]
• values[i] = [values_group_0, values_group_1, ...]

Где:

• weights_group_i[j] = вес j-го элемента i-й группы
• values_group_i[j] = значение j-го элемента i-й группы

Это будут входы knapsack_multichoice_onepick. Вот пример:

# Example
values = [[6, 10], [12, 2], [2, 3]]
weights = [[1, 2], [6, 2], [3, 2]]
W = 7

print(knapsack_multichoice_onepick(weights, values, W))  # (15, [(0, 1), (1, 1), (2, 1)])

После этого я последовал предложению @user3386109 и сделал комбинации с индексами. Методы групповой предварительной обработки: players_preproc, generate_group и group_preproc.

Опять же, этот код предназначен для примера, где у вас есть Fantasy League с playersDB, где у каждого игрока есть цена (вес), очки (значение) и позиция (группа); есть список possible_formations (групповых вариаций); и budget (W) вы не можете перейти.

Метод best_full_teams печатает все и использует все предыдущие.