Может ли ChatGPT решать задачи о рюкзаке?
Can ChatGPT solve knapsack problems?
Решение проблем операционного исследования (OR) с помощью ChatGPT
С момента появления ChatGPT я задумывался о том, как ChatGPT повлияет на мир оптимизации и операционного исследования (OR). Были новости о том, что ChatGPT сдал экзамены по математике средней школы и бакалавриата, что вызвало мой интерес к исследованию его способности решать проблемы OR. В этой статье я буду использовать классическую проблему OR – проблему 0/1 рюкзака, чтобы провести некоторые тесты.
Проблема рюкзака
В области оптимизации и проблем выбора рюкзака давно стоит классический бенчмарк – проблема рюкзака. Она вызывает нас выбрать комбинацию предметов, каждый со своим весом и стоимостью, таким образом, чтобы максимизировать общую стоимость, оставаясь в заданном ограничении веса. Динамическое программирование – это эффективный алгоритм, который мы обычно используем для решения проблем 0/1 рюкзака.
Разговор с ChatGPT
Я начал с очень маленького примера и попросил ChatGPT его решить.
Я: Рассмотрим проблему рюкзака, где вместимость рюкзака составляет 10 фунтов. У меня есть 4 предмета на выбор, стоимость которых составляет $10, $40, $30, $50, а вес – 5 фунтов, 4 фунта, 6 фунтов, 3 фунта соответственно. Можете ли вы решить эту проблему для меня?
- Исследователи IBM предлагают новую атакующую рамку, способную генерировать атакующие входы для систем искусственного интеллекта независимо от модальности или задачи.
- Революционизация настройки 3D моделей с использованием искусственного интеллекта исследователи Массачусетского технологического института разработали удобный интерфейс для эстетических изменений без влияния на функциональность.
- Исследователи Google представляют новый подход искусственного интеллекта к моделированию предпочтения изображения в динамике сцены
ChatGPT: Конечно! Проблема рюкзака – это классическая оптимизационная задача, целью которой является максимизация общей стоимости выбранных предметов для рюкзака с учетом ограничения на общий вес выбранных предметов, который не должен превышать вместимость рюкзака.
В вашем случае у вас есть 4 предмета со своими стоимостями и весами:
Предмет 1: Стоимость = $10, Вес = 5 фунтов Предмет 2: Стоимость = $40, Вес = 4 фунта Предмет 3: Стоимость = $30, Вес = 6 фунтов Предмет 4: Стоимость = $50, Вес = 3 фунта
Вместимость рюкзака = 10 фунтов
Для решения этой проблемы вы можете использовать метод динамического программирования. Создайте 2D-таблицу, где строки представляют предметы, а столбцы представляют оставшиеся вместимости рюкзака (от 0 до 10 фунтов). Заполните таблицу итеративно, чтобы найти максимальную стоимость, которую можно получить для каждой комбинации предметов и оставшихся вместимостей.
Вот процесс заполнения таблицы:
| Вме | стим | ость | (фу | нты) 0 | 1 2 | 3 4 | 5 6 | 7 8 | 9 1 | 0 – | – – | – – | – – | – – | – – | – – | – |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| — | — | — | — | Пред | мет 1 ( | 5 фунтов | ) 0 | 0 0 | 0 0 | 10 1 | 0 10 | 10 | 10 1 | 0Пред | мет 2 | (4 фунта | ) 0 |
| 0 0 | 0 40 | 40 | 40 4 | 0 50 | 50 | 50П | редмет 3 | (6 | фунтов) | 0 0 | 0 0 | 40 4 | 0 30 | 70 | 70 7 | 0 70 | Предмет |
| 4 (3 | фунта) | 0 0 | 0 5 | 0 50 | 50 | 50 7 | 0 70 | 70 | 80 |
Таблица показывает максимальное значение, которое может быть получено для каждой комбинации предметов и оставшихся вместимостей. Конечная ячейка (внизу справа) имеет значение $80, которое является максимальным значением, которое можно получить с вместимостью рюкзака в 10 фунтов.
Чтобы найти предметы, которые следует выбрать, вы можете вернуться от последней ячейки к первой, учитывая решения, приведшие к максимальному значению. В этом случае вы бы выбрали Предмет 2 и Предмет 4, которые имеют общую стоимость $40 + $50 = $90 и общий вес 4 фунта + 3 фунта = 7 фунтов, что в пределах вместимости рюкзака в 10 фунтов.
Таким образом, оптимальным решением является выбор Предмета 2 и Предмета 4, что дает общую стоимость $90.
Очевидно, что ChatGPT способен выбрать правильный подход для решения этой проблемы, но окончательное решение, предложенное ChatGPT, не соответствует его логическому процессу. В частности, таблица динамического программирования (DP) показывает $80 (нижняя правая ячейка) как оптимальное целевое значение, но ChatGPT заключил, что $90 – это окончательный ответ.
Чтобы проверить, какое решение является правильным, я написал следующий фрагмент кода на Python, чтобы выполнить алгоритм DP.
import numpy as npv = [10, 40, 30, 50]w = [5, 4, 6, 3]c = 10dp = np.zeros((5,11))for i in range(1,5): for j in range(1,11): if j < w[i-1]: dp[i,j] = dp[i-1,j] else: dp[i,j] = max(dp[i-1,j],dp[i-1,j-w[i-1]]+v[i-1]) dp[1:,1:]Выведенная таблица DP выглядит следующим образом.
Это подтверждает, что заключение, к которому пришел ChatGPT, является правильным, но таблица DP, предложенная ChatGPT, неправильная. Затем я продолжил просить его исправить таблицу DP.
Я: Я думаю, что ваше решение правильное, но в таблице есть ошибки.
ChatGPT: Извините за возможную путаницу. Позвольте мне исправить таблицу для вас. Вот исправленная таблица динамического программирования для задачи о рюкзаке:
| Вмес | ти- | лимо | сти | (фу | нк | ты | ) 0 | 1 2 | 3 4 | 5 6 | 7 8 | 9 1 | 0 – | – – | – – | – – | – – | – – | – – | – – | – |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| — | — | — | — | Пред | мет | 1 ( | 5фу | нт | ) 0 | 0 0 | 0 0 | 10 1 | 0 10 | 10 | 10 1 | 0Пред | мет 2 | (4фу | нт | ы) 0 | |
| 0 0 | 0 40 | 40 | 40 4 | 0 40 | 50 | 50П | редмет | 3 (6фу | нт | 0 0 | 0 0 | 40 4 | 0 40 | 40 | 40 5 | 0 70 | Пред | ||||
| 4 (3 | фу | нт | 0 0 | 0 5 | 0 50 | 50 | 90 9 | 0 90 | 90 | 90 |
Теперь таблица верна. Значение в нижней правой ячейке составляет $90, что представляет собой максимальное значение, которое можно получить при вместимости рюкзака 10 фунтов. Как уже упоминалось ранее, оптимальным решением является выбор Предмета 2 и Предмета 4, что дает вам общую стоимость $90.
Интересно, что ChatGPT способен вносить некоторые исправления в таблицу, чтобы нижняя правая ячейка совпадала с $90. Однако, если мы рассмотрим таблицу более пристально, последняя строка таблицы все еще некорректна. Ячейка в 4-й строке и 7-м столбце (соответствующая вместимости рюкзака 6 фунтов) должна быть $50 вместо $90. Рюкзак вместимостью 6 фунтов не позволит нам выбрать предметы 2 и 4 для достижения $90, так как общий вес предметов 2 и 4 составляет 7 фунтов, что превышает вместимость рюкзака.
Затем я попросил его написать некоторый код для решения этой проблемы.
Я: Не могли бы вы написать код на Python для решения этой проблемы?
ChatGPT: Конечно! Вы можете решить проблему 0/1 рюкзака с использованием динамического программирования на Python. Вот фрагмент кода на Python для решения проблемы на основе предоставленного вами конкретного случая:
def knapsack(values, weights, capacity): n = len(values) # Инициализируем таблицу для хранения максимальных значений для разных вместимостей dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(capacity + 1): # Если вес текущего предмета больше текущей вместимости, пропустить его if weights[i - 1] > w: dp[i][w] = dp[i - 1][w] else: # Выберите максимальное значение между включением и исключением текущего предмета dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) # Восстановление выбранных предметов selected_items = [] i, w = n, capacity while i > 0 and w > 0: if dp[i][w] != dp[i - 1][w]: selected_items.append(i - 1) w -= weights[i - 1] i -= 1 return dp[n][capacity], selected_items# Значения и веса предметовvalues = [10, 40, 30, 50]weights = [5, 4, 6, 3]knapsack_capacity = 10max_value, selected_items = knapsack(values, weights, knapsack_capacity)print(f"Максимальное значение: ${max_value}")print("Выбранные предметы:")for i in selected_items: print(f"Предмет {i + 1} (Значение: ${values[i]}, Вес: {weights[i]} фунтов)")При запуске этого кода он будет выводить максимальное значение и выбранные предметы, которые следует поместить в рюкзак. В вашем конкретном случае он правильно выберет Предмет 2 и Предмет 4, которые имеют общую стоимость $90 и общий вес 7 фунтов, в пределах вместимости рюкзака 10 фунтов.
Этот код печатает оптимальное решение четко и правильно. Таблица DP, вычисленная этим кодом, также является правильной.
Затем я пошел дальше и протестировал другой случай, проблему рюкзака с вместимостью 500 фунтов и 10 предметами на выбор. Значение и вес каждого предмета генерируются случайным образом с использованием следующего кода.
import numpy as npnp.random.seed(0)w = np.random.normal(10, 3, 100)w = [int(x) if x>= 1 else 1 for x in w]v = np.random.normal(100, 30, 100)v = [int(x) if x>= 10 else 10 for x in v]dp = np.zeros((101,501))for i in range(1,101): for j in range(1,501): if j < w[i-1]: dp[i,j] = dp[i-1,j] else: dp[i,j] = max(dp[i-1,j],dp[i-1,j-w[i-1]]+v[i-1]) dp[1:,1:]Я скопировал и вставил сгенерированные значения и веса, и попросил ChatGPT решить эту проблему.
Я: Рассмотрим задачу о рюкзаке, в которой вместимость рюкзака составляет 500 фунтов. У меня есть 100 предметов, из которых нужно выбрать, их значения заданы списком [156, 59, 61, 129, 64, 158, 87, 77, 157, 144, 156, 127, 74, 157, 91, 124, 128, 95, 118, 127, 111, 67, 108, 139, 79, 95, 86, 155, 120, 112, 76, 116, 79, 100, 80, 120, 117, 93, 111, 67, 55, 113, 105, 119, 171, 128, 72, 133, 60, 86, 97, 151, 77, 75, 97, 80, 133, 67, 65, 86, 85, 157, 128, 102, 63, 125, 69, 53, 135, 109, 127, 109, 125, 80, 68, 120, 75, 79, 86, 100, 89, 58, 80, 33, 118, 51, 66, 101, 77, 146, 61, 108, 98, 64, 115, 94, 123, 124, 164, 140], а их веса заданы списком [15, 11, 12, 16, 15, 7, 12, 9, 9, 11, 10, 14, 12, 10, 11, 11, 14, 9, 10, 7, 2, 11, 12, 7, 16, 5, 10, 9, 14, 14, 10, 11, 7, 4, 8, 10, 13, 13, 8, 9, 6, 5, 4, 15, 8, 8, 6, 12, 5, 9, 7, 11, 8, 6, 9, 11, 10, 10, 8, 8, 7, 8, 7, 4, 10, 8, 5, 11, 7, 10, 12, 10, 13, 6, 11, 7, 7, 8, 9, 10, 6, 12, 11, 5, 14, 15, 13, 9, 6, 13, 8, 13, 10, 12, 11, 12, 10, 15, 10, 11] соответственно. Можете ли вы решить эту задачу для меня?
ChatGPT: Решение задачи о рюкзаке для 100 предметов с вместимостью 500 фунтов является вычислительно сложной задачей. Однако, я могу предоставить вам код на Python для решения этой задачи с использованием динамического программирования. Однако, имейте в виду, что его выполнение может занять некоторое время.
Вот код на Python для решения задачи о рюкзаке с предоставленными значениями и весами:
def knapsack(values, weights, capacity): n = len(values) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(capacity + 1): if weights[i - 1] > w: dp[i][w] = dp[i - 1][w] else: dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) selected_items = [] i, w = n, capacity while i > 0 and w > 0: if dp[i][w] != dp[i - 1][w]: selected_items.append(i - 1) w -= weights[i - 1] i -= 1 return dp[n][capacity], selected_items# Значения и веса предметовvalues = [ 156, 59, 61, 129, 64, 158, 87, 77, 157, 144, 156, 127, 74, 157, 91, 124, 128, 95, 118, 127, 111, 67, 108, 139, 79, 95, 86, 155, 120, 112, 76, 116, 79, 100, 80, 120, 117, 93, 111, 67, 55, 113, 105, 119, 171, 128, 72, 133, 60, 86, 97, 151, 77, 75, 97, 80, 133, 67, 65, 86, 85, 157, 128, 102, 63, 125, 69, 53, 135, 109, 127, 109, 125, 80, 68, 120, 75, 79, 86, 100, 89, 58, 80, 33, 118, 51, 66, 101, 77, 146, 61, 108, 98, 64, 115, 94, 123, 124, 164, 140]weights = [ 15, 11, 12, 16, 15, 7, 12, 9, 9, 11, 10, 14, 12, 10, 11, 11, 14, 9, 10, 7, 2, 11, 12, 7, 16, 5, 10, 9, 14, 14, 10, 11, 7, 4, 8, 10, 13, 13, 8, 9, 6, 5, 4, 15, 8, 8, 6, 12, 5, 9, 7, 11, 8, 6, 9, 11, 10, 10, 8, 8, 7, 8, 7, 4, 10, 8, 5, 11, 7, 10, 12, 10, 13, 6, 11, 7, 7, 8, 9, 10, 6, 12, 11, 5, 14, 15, 13, 9, 6, 13, 8, 13, 10, 12, 11, 12, 10, 15, 10, 11]вместимость_рюкзака = 500максимальное_значение, выбранные_предметы = knapsack(values, weights, вместимость_рюкзака)print(f"Максимальное значение: {максимальное_значение}")print("Выбранные предметы:")for i in выбранные_предметы: print(f"Предмет {i + 1} (Значение: {values[i]}, Вес: {weights[i]})")Запуск этого кода предоставит вам максимальное значение, которое может быть получено, и список выбранных элементов. Пожалуйста, будьте терпеливы, так как выполнение может занять некоторое время.
На этот раз, вместо того, чтобы непосредственно решать проблему и давать мне ответ, он дал мне некоторый код на Python для выполнения. Код хорошо работает при решении этой проблемы.
Заключение
Это моя первая попытка понять способность ChatGPT решать сложные математические проблемы, такие как классическая проблема OR – проблема о рюкзаке. Кажется, что для небольших экземпляров проблемы о рюкзаке он способен дать ответ оптимального решения. Однако качество ответа не всегда гарантировано. В процессе рассуждения или в конечном ответе могут возникать ошибки. Для больших экземпляров ChatGPT, как правило, избегает прямого ответа на оптимальное решение, а вместо этого дает кусок кода для выполнения. Код обычно хорошо написан и дает нам правильное решение. Поэтому, когда решаете проблемы о рюкзаке с помощью ChatGPT, не полагайтесь слишком сильно на прямой ответ оптимального решения, который он дает, а вместо этого запускайте предоставленный им код для дополнительной проверки.
.webp)
