СА LAB 1

LAB #1. Решение задачи о рюкзаке

Задача о рюкзаке — это классическая проблема комбинаторной оптимизации, где требуется выбрать набор предметов с максимальной ценностью при ограничении по весу.
Основные характеристики задачи:

Каждый предмет имеет вес и стоимость
Предметы нельзя делить на части
Можно брать каждый предмет только один раз
Цель — максимизировать общую стоимость при соблюдении весового ограничения

Формулировка задачи о рюкзаке

Классическая постановка задачи

Задача о рюкзаке (Knapsack problem) — это одна из классических задач комбинаторной оптимизации. Суть задачи заключается в выборе предметов для помещения в рюкзак с ограниченной вместимостью таким образом, чтобы максимизировать общую ценность выбранных предметов.

Математическая формулировка

Дано:

Множество предметов n
Для каждого предмета i известны:
- Вес w_i
- Ценность (стоимость) v_i
Вместимость рюкзака C

Требуется:

Найти такой набор предметов, который:

Не превышает вместимость рюкзака
Обеспечивает максимальную суммарную ценность

Формальная запись

Целевая функция:

Максимизировать:

max ∑_i=1ⁿ v_ix_i

При ограничениях:

Ограничение по вместимости:
∑_i=1ⁿ w_ix_i ≤ C
Ограничения на переменные:
x_i ∈ {0,1}, i = 1,2,...,n

где x_i — бинарная переменная:

x_i = 1, если предмет включен в рюкзак
x_i = 0, если предмет не включен

Варианты задачи

Базовый вариант (0-1 рюкзак): каждый предмет можно взять не более одного раза
Неограниченный вариант: предметы можно брать неограниченное количество раз
Многомерный рюкзак: учитываются несколько ограничений (вес, объем, стоимость)
Фракционный рюкзак: предметы можно разбивать на части

Аналитическое решение

Метод динамического программирования

Наиболее эффективный способ решения задачи о рюкзаке — использование динамического программирования.

Алгоритм решения:

Создание таблицы M[i,j], где:

i — номер предмета
j — текущий вес рюкзака

Заполнение таблицы по формуле:
M[i,j] = max(M[i-1,j], v_i + M[i-1,j-w_i])
Базовые случаи:
- M[0,j] = 0 для всех j
- M[i,0] = 0 для всех i

Шаги решения:

Инициализация массива M
Последовательное заполнение таблицы
Восстановление решения из таблицы

Временная сложность:

Алгоритм работает за время O(nC), где:

n — количество предметов
C — вместимость рюкзака

Пример реализации:

Псевдокод решения:

function knapsack(values, weights, n, C):
    create array M[n+1][C+1]
    
    for i from 0 to n:
        M[i][0] = 0
    
    for j from 0 to C:
        M[0][j] = 0
    
    for i from 1 to n:
        for j from 1 to C:
            if weights[i] <= j:
                M[i][j] = max(M[i-1][j], values[i] + M[i-1][j-weights[i]])
            else:
                M[i][j] = M[i-1][j]
    
    return M[n][C]

Особенности применения:

Метод эффективен для задач среднего размера
Требует большого объема памяти
Гарантирует нахождение оптимального решения

Решение задачи о рюкзаке в MATLAB

Использование функции intlinprog

MATLAB предоставляет встроенную функцию intlinprog для решения задач целочисленного линейного программирования по умолчанию использующую метод ветвей и границ.

Шаг 1: Подготовка данных

Пример входных данных:

% Вектор ценностей предметов
v = [15 20 30 40];

% Вектор весов предметов
w = [1 2 3 4];

% Вместимость рюкзака
C = 6;

% Количество предметов
n = length(v);

Шаг 2: Формулировка задачи

Настройка параметров для intlinprog:

% Целевая функция (максимизация, поэтому берем с минусом)
f = -v;

% Матрица ограничений
A = w;

% Правая часть ограничения
b = C;

% Индексы целочисленных переменных
intcon = 1:n;

% Границы для переменных (0 или 1)
lb = zeros(1,n);
ub = ones(1,n);

Шаг 3: Решение задачи

Вызов функции intlinprog:

% Решение задачи
[x, fval] = intlinprog(f, intcon, A, b, [], [], lb, ub);

% Вывод результатов
disp('Включенные предметы:');
disp(find(x == 1));

disp(['Максимальная ценность: ', num2str(-fval)]);

Интерпретация результатов

Вектор x содержит решение (1 - предмет включен, 0 - нет)

Значение fval показывает максимальную ценность

Важные замечания

Функция intlinprog ищет минимум, поэтому целевая функция берется с минусом

Все переменные должны быть целочисленными

Ограничения задаются в виде Ax ≤ b

Графическое решение задачи методом полного перебора

Суть метода

Метод полного перебора (brute force) заключается в переборе всех возможных комбинаций предметов и выборе оптимального решения.

Алгоритм решения

Генерация всех возможных подмножеств предметов
Проверка каждого подмножества на соответствие ограничениям
Выбор подмножества с максимальной ценностью

Визуализация процесса

Пример построения дерева решений:

                     []
                   /    \
                  /      \
                 /        \
              [1]         []
            /   \       /    \
           /     \     /      \
       [1,2]    [1]  [2]      []
      /   \    /  \  /  \    /  \
  [1,2,3][1,2][1,3][1] [2,3][2][]

Реализация алгоритма

Пример кода для перебора:

function bruteForceKnapsack(values, weights, C)
    n = length(values);
    maxValue = 0;
    bestSet = [];
    
    % Перебираем все комбинации от 0 до 2^n-1
    for i = 0:(2^n - 1)
        currentSet = dec2bin(i, n) - '0';
        totalWeight = sum(currentSet .* weights);
        totalValue = sum(currentSet .* values);
        
        if totalWeight <= C && totalValue > maxValue
            maxValue = totalValue;
            bestSet = currentSet;
        end
    end
    
    return bestSet, maxValue;
end

Графическое представление

Каждый узел дерева — это возможная комбинация предметов
Левая ветвь — предмет включен
Правая ветвь — предмет не включен

Особенности метода

Гарантирует нахождение оптимального решения
Имеет экспоненциальную сложность O(2^n)
Подходит для малого количества предметов (< 20)

Практические рекомендации

Использовать для задач небольшого размера
Оптимизировать с помощью отсечения
Применять для проверки других алгоритмов

Полное решение задачи о рюкзаке с визуализацией

Исходные данные

Начальные параметры задачи:

weights = [45, 60, 95, 50, 80]; % веса предметов
values = [25, 30, 45, 28, 35]; % стоимости предметов
capacity = 270; % вместимость рюкзака
n = length(weights); % количество предметов

Генерация комбинаций

Создание всех возможных комбинаций:

all_combinations = dec2bin(0:(2^n-1)) - '0';
num_combinations = size(all_combinations, 1);

Расчет параметров

Вычисление веса и стоимости для каждой комбинации:

total_weights = zeros(num_combinations, 1);
total_values = zeros(num_combinations, 1);

for i = 1:num_combinations
    selected_items = all_combinations(i, :);
    total_weights(i) = sum(selected_items .* weights);
    total_values(i) = sum(selected_items .* values);
end

Фильтрация решений

Отбор допустимых комбинаций:

valid_indices = total_weights <= capacity;
valid_weights = total_weights(valid_indices);
valid_values = total_values(valid_indices);

Поиск оптимального решения

Определение наилучшего варианта:

[max_value, max_index] = max(valid_values);
optimal_weight = valid_weights(max_index);
optimal_combination = all_combinations(max_index, :);

Визуализация результатов

Построение графика:

figure;
hold on;
plot(valid_weights, valid_values, 'bo', 'MarkerFaceColor', [0.5 0.5 0.5]);
plot(optimal_weight, max_value, 'ro', 'MarkerSize', 10);

xlim([0, capacity]);
ylim([0, max(valid_values) + 10]);
xlabel('Общий вес');
ylabel('Общая стоимость');
title('Графическое решение задачи о рюкзаке');
grid on;

Вывод результатов

Финальные результаты:

fprintf('Оптимальное решение:\n');
fprintf('Выбранные предметы: %s\n', mat2str(optimal_combination));
fprintf('Максимальная стоимость: %d\n', max_value);
fprintf('Общий вес: %d\n', optimal_weight);

Особенности реализации

Используется полный перебор всех комбинаций
Визуализация допустимых решений
Выделение оптимального решения
Автоматический расчет параметров

Практическое применение

Обучение принципам решения задачи

Визуальный анализ решений

Проверка корректности алгоритмов

Задание

балл: 0
описание:
- С любых открытых источников создать набор данных 20-30 предметов. столбец номер, наименование, вес.
- Экспортировать данные в матлаб или "ручками"
балл: 1

intlinprog
описание:
- реализация решения с использование intlinprog, объем рюкзака 30-70% от веса всего набора данных
балл: 1

Графическое решение
описание:
- реализация решения графически, объем рюкзака 30-70% от веса всего набора данных