Задача 4. В рюкзак объема V=10 кладут N=5 групп предметов. Объемы, веса и количество предметов в каждой группе приведены в таблице:
| Γ{1} | Γ{2} | Γ{3} | Γ{4} | Γ{5} | |
|---|---|---|---|---|---|
| Объем v{k} | 3 | 2 | 1 | 2 | 4 |
| Вес p{k} | 2 | 3 | 2 | 4 | 3 |
| Количество n{k} | 4 | 2 | 3 | 1 | 3 |
Найдем оптимальный выбор предметов, чтобы суммарный объём не превышал 10, а суммарный вес (ценность) был максимальным.
Дано 5 групп с параметрами:
Группа 1: объём v₁ = 3, вес p₁ = 2, доступно n₁ = 4 Группа 2: объём v₂ = 2, вес p₂ = 3, доступно n₂ = 2 Группа 3: объём v₃ = 1, вес p₃ = 2, доступно n₃ = 3 Группа 4: объём v₄ = 2, вес p₄ = 4, доступно n₄ = 1 Группа 5: объём v₅ = 4, вес p₅ = 3, доступно n₅ = 3
Общий объём рюкзака V = 10.
Шаг 1. Определим удельную ценность (отношение веса к объёму) для каждой группы: • Группа 1: 2/3 ≈ 0.67 • Группа 2: 3/2 = 1.5 • Группа 3: 2/1 = 2....