Онлайн розв'язувач задачі про рюкзак 0/1

Розв'язування задачі про рюкзак 0/1

Задача про рюкзак 0/1 виникає, коли з набору предметів із заданими вагами та цінностями потрібно обрати підмножину, що не перевищує місткість рюкзака та має максимальну сумарну цінність. Кожен предмет можна взяти не більше одного разу.

Приклад роботи

Нехай задано предмети: A (вага 2, цінність 6), B (вага 3, цінність 10), C (вага 4, цінність 12). Місткість рюкзака — 5. Розв'язувач поверне максимальну цінність 16 та набір предметів A і B.

Алгоритм та обмеження

Інструмент використовує метод динамічного програмування для точного розв'язання. Він не розглядає дробові частини, кратні предмети, багатовимірні обмеження чи валютні особливості. Якщо існує кілька оптимальних наборів з однаковою цінністю, буде показано лише один із них, без додаткових критеріїв (наприклад, найменшої ваги).

Практичні поради

• Переконайтеся, що ваги — додатні цілі числа, а цінності можуть бути нулем.
• Назви предметів мають бути унікальними, інакше інструмент повідомить про помилку.
• Якщо потрібно порівняти кілька варіантів, запускайте розрахунок окремо для кожного набору даних.

Поширені запитання

Чи можна використовувати від'ємні ваги або цінності?

Ні, ваги мають бути додатними цілими числами, а цінності — від 0 до 1000000000. Від'ємні значення не підтримуються.

Що робити, якщо є кілька оптимальних наборів?

Інструмент показує лише один оптимальний набір. Він не перелічує всі можливі варіанти та не застосовує додаткові критерії, як-от мінімальна вага.

Чи підтримує інструмент дробові предмети або кратність?

Ні, це розв'язувач задачі 0/1: кожен предмет можна взяти не більше одного разу, і вага завжди ціла. Для дробових або кратних задач використовуйте інші методи.