Made on
Tilda
Задача о рюкзаке (Knapsack problem) — это одна из классических задач комбинаторной оптимизации. Суть задачи заключается в выборе предметов для помещения в рюкзак с ограниченной вместимостью таким образом, чтобы максимизировать общую ценность выбранных предметов.
Найти такой набор предметов, который:
Максимизировать:
где xi — бинарная переменная:
Наиболее эффективный способ решения задачи о рюкзаке — использование динамического программирования.
Алгоритм работает за время O(nC), где:
Псевдокод решения:
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]
Проверяем все возможные комбинации предметов и выбираем наилучшую.
Даны предметы:
Комбинации с одним предметом:
Комбинации с двумя предметами:
Комбинация с тремя предметами:
Максимальная ценность = 80 (комбинация {1,3})
Алгоритм основан на последовательном выборе предметов по убыванию ценности на единицу веса.
Используем те же предметы:
Общая ценность = 70
Вес = 5 кг
// Входные данные
вес = [2 3 5]; // веса предметов
ценность = [30 40 50]; // ценности предметов
max_вес = 6; // максимальный вес рюкзака
// Количество предметов
n = length(вес);
// Перебираем все возможные комбинации
for i = 0:(2^n - 1)
// Преобразуем число в двоичный код
bin = string(dec2bin(i, n));
// Вычисляем вес и ценность текущей комбинации
текущий_вес = 0;
текущая_ценность = 0;
// Исправленный цикл по символам строки
for j = 1:length(bin)
if part(bin, j) == '1' then
текущий_вес = текущий_вес + вес(j);
текущая_ценность = текущая_ценность + ценность(j);
end
end
// Проверяем, подходит ли комбинация
if текущий_вес <= max_вес then
// Выводим результат
disp("Комбинация: " + bin);
disp("Вес: " + string(текущий_вес));
disp("Ценность: " + string(текущая_ценность));
disp("------------------------");
end
end
| Комбинация | Вес | Ценность | Допустимость |
|---|---|---|---|
| 000 | 0 | 0 | Допустима |
| 001 | 5 | 50 | Допустима |
| 010 | 3 | 40 | Допустима |
| 011 | 8 | 90 | Недопустима |
| 100 | 2 | 30 | Допустима |
| 101 | 7 | 80 | Недопустима |
| 110 | 5 | 70 | Допустима |
| 111 | 10 | 120 | Недопустима |
Лучшая комбинация: 110
Максимальная ценность: 70
Общий вес: 5 кг
Комбинация 110 означает, что мы берем:
// Входные данные
вес = 2 3 5; // веса предметов
ценность = 30 40 50; // ценности предметов
max_вес = 6; // максимальный вес рюкзака
// Количество предметов
n = length(вес);
// Переменные для поиска максимума
max_ценность = 0;
лучшая_комбинация = "";
// Перебираем все возможные комбинации
for i = 0:(2^n - 1)
// Преобразуем число в двоичный код
bin = string(dec2bin(i, n));
// Вычисляем вес и ценность текущей комбинации
текущий_вес = 0;
текущая_ценность = 0;
// Цикл по символам строки
for j = 1:length(bin)
if part(bin, j) == '1' then
текущий_вес = текущий_вес + вес(j);
текущая_ценность = текущая_ценность + ценность(j);
end
end
// Проверяем, подходит ли комбинация
if текущий_вес <= max_вес then
// Обновляем максимум
if текущая_ценность > max_ценность then
max_ценность = текущая_ценность;
лучшая_комбинация = bin;
end
end
end
// Выводим результат
disp("Лучшая комбинация: " + лучшая_комбинация);
disp("Максимальная ценность: " + string(max_ценность));
Код сохраняет только лучшую найденную комбинацию, сравнивая каждую новую допустимую комбинацию с текущей максимальной ценностью.
Метод полного перебора позволяет найти оптимальное решение задачи о рюкзаке путем проверки всех возможных комбинаций. Оптимизированный код делает этот процесс более эффективным, автоматически находя наилучшее решение.
| Вариант | Тип транспорта | Вместимость | Груз 1 | Груз 2 | Груз 3 | Груз 4 | Груз 5 | Груз 6 |
|---|---|---|---|---|---|---|---|---|
| 1 | Автовоз | 5000 кг | 1000 кг (25000 руб) | 1300 кг (32500 руб) | 800 кг (20000 руб) | 900 кг (22500 руб) | 700 кг (17500 руб) | 300 кг (7500 руб) |
| 2 | Платформа для негабаритных грузов | 90 т | 20 т (600000 руб) | 28 т (840000 руб) | 18 т (540000 руб) | 15 т (450000 руб) | 8 т (240000 руб) | 11 т (330000 руб) |
| 3 | Рефрижератор | 30 т | 7.5 т (225000 руб) | 8.5 т (255000 руб) | 6.2 т (186000 руб) | 5.3 т (159000 руб) | 2.5 т (75000 руб) | 3.5 т (105000 руб) |
| 4 | Микроавтобус | 1000 кг | 250 кг (5000 руб) | 300 кг (6000 руб) | 200 кг (4000 руб) | 150 кг (3000 руб) | 100 кг (2000 руб) | 50 кг (1000 руб) |
| 5 | Грузовой вертолет | 65 т | 25 т (750000 руб) | 22 т (660000 руб) | 18 т (540000 руб) | 10 т (300000 руб) | 6 т (180000 руб) | 4 т (120000 руб) |
| 6 | Сухогруз | 2500 т | 600 т (1800000 руб) | 550 т (1650000 руб) | 450 т (1350000 руб) | 350 т (1050000 руб) | 300 т (900000 руб) | 250 т (750000 руб) |
| 7 | Изотермический вагон | 55 т | 12 т (360000 руб) | 15 т (450000 руб) | 10 т (300000 руб) | 8 т (240000 руб) | 7 т (210000 руб) | 3 т (90000 руб) |
| 8 | Контейнеровоз | 40 т | 10 т (300000 руб) | 9 т (270000 руб) | 8 т (240000 руб) | 7 т (210000 руб) | 4 т (120000 руб) | 2 т (60000 руб) |
| 9 | Трамвай грузовой | 1500 кг | 350 кг (7000 руб) | 400 кг (8000 руб) | 300 кг (6000 руб) | 250 кг (5000 руб) | 150 кг (3000 руб) | 50 кг (1000 руб) |
| 10 | Мультимодальный модуль | 28 т | 8 т (240000 руб) | 7.5 т (225000 руб) | 6 т (180000 руб) | 5 т (150000 руб) | 1 т (30000 руб) | 0.5 т (15000 руб) |