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 |
|---|---|---|---|---|---|---|
| 1 | Грузовой автомобиль | 3500 кг | 800 кг (15000 руб) | 1200 кг (20000 руб) | 650 кг (12000 руб) | 950 кг (18000 руб) |
| 2 | Железнодорожный вагон | 65 т | 15 т (450000 руб) | 22 т (600000 руб) | 18 т (540000 руб) | 12 т (360000 руб) |
| 3 | Морской контейнер | 28 т | 7.5 т (225000 руб) | 9.2 т (276000 руб) | 6.8 т (204000 руб) | 4.5 т (135000 руб) |
| 4 | Небольшой грузовик | 1200 кг | 300 кг (9000 руб) | 450 кг (13500 руб) | 280 кг (8400 руб) | 320 кг (9600 руб) |
| 5 | Самолет | 85 т | 25 т (750000 руб) | 32 т (960000 руб) | 18 т (540000 руб) | 20 т (600000 руб) |
| 6 | Речная баржа | 150 т | 45 т (1350000 руб) | 55 т (1650000 руб) | 30 т (900000 руб) | 20 т (600000 руб) |
| 7 | Городской фургон | 800 кг | 200 кг (6000 руб) | 250 кг (7500 руб) | 180 кг (5400 руб) | 220 кг (6600 руб) |
| 8 | Автоконтейнер | 22 т | 6.5 т (195000 руб) | 7.2 т (216000 руб) | 5.8 т (174000 руб) | 2.5 т (75000 руб) |
| 9 | Железнодорожный контейнер | 45 т | 12 т (360000 руб) | 15 т (450000 руб) | 10 т (300000 руб) | 8 т (240000 руб) |
| 10 | Морской сухогруз | 5000 т | 1500 т (4500000 руб) | 1800 т (5400000 руб) | 1200 т (3600000 руб) | 500 т (1500000 руб) |