В мире информатики структуры данных и алгоритмы играют решающую роль в эффективном решении сложных задач. Одной из таких задач является задача «мешка с золотом», которая предполагает нахождение максимальной ценности из набора золотых слитков разного веса. В этой статье мы рассмотрим различные методы решения проблемы мешка с золотом, а также приведем примеры кода на Python.

Метод 1: грубая сила
Подход грубой силы включает в себя создание всех возможных комбинаций золотых слитков и расчет общей стоимости для каждой комбинации. Комбинация с максимальным значением считается оптимальным решением. Хотя этот метод работает для небольших входных данных, он становится неэффективным для больших наборов данных из-за экспоненциальной временной сложности.

def brute_force_bag_of_gold(weights, values, capacity):
    n = len(weights)
    max_value = 0
    # Generate all combinations
    for i in range(2  n):
        current_weight = 0
        current_value = 0
        # Calculate weight and value for each combination
        for j in range(n):
            if (i >> j) & 1:
                current_weight += weights[j]
                current_value += values[j]
        # Update max value if current combination is valid and has higher value
        if current_weight <= capacity and current_value > max_value:
            max_value = current_value
    return max_value

Метод 2: динамическое программирование
Динамическое программирование предлагает оптимизированное решение путем разбиения проблемы на более мелкие подзадачи и повторного использования решений. Задачу о мешке с золотом можно решить с помощью подхода динамического программирования, известного как задача о рюкзаке 0/1.

def dynamic_programming_bag_of_gold(weights, values, capacity):
    n = len(weights)
    # Initialize a 2D array to store optimal values
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] > j:
                dp[i][j] = dp[i - 1][j]  # Exclude the current gold bar
            else:
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])
    return dp[n][capacity]

Метод 3: Жадный алгоритм
Жадный алгоритм выбирает золотые слитки на основе их соотношения стоимости к весу, сначала выбирая те, у которых это соотношение самое высокое. Однако жадный подход не всегда гарантирует оптимальное решение проблемы мешка с золотом.

def greedy_bag_of_gold(weights, values, capacity):
    n = len(weights)
    ratios = [(values[i] / weights[i], i) for i in range(n)]
    ratios.sort(reverse=True)
    max_value = 0
    current_weight = 0
    for ratio, index in ratios:
        if current_weight + weights[index] <= capacity:
            current_weight += weights[index]
            max_value += values[index]
    return max_value

Проблему мешка с золотом можно решить различными методами, включая грубую силу, динамическое программирование и жадные алгоритмы. Хотя метод грубой силы прост, но неэффективен, динамическое программирование обеспечивает оптимизированное решение, разбивая проблему на более мелкие подзадачи. Жадный алгоритм предлагает эвристическое решение, выбирая золотые слитки на основе соотношения стоимости к весу. Каждый метод имеет свои преимущества и ограничения, и выбор метода зависит от ограничений задачи и размера входных данных.