Алгоритм укладки рюкзака Python
Писал небольшую программу для подсчета профиля. Использовал вариацию алгоритма укладка рюкзака - алгоритм золотых слитков, так как он описан везде. При определенном наборе данных он работает не корректно.
A = [22, 25, 34, 56, 72, 76, 115, 122, 127, 138, 139, 145, 167, 267, 267]
S = 300
F = [[0] *2 for i in range(S + 1)]
F[0][0] = 1
for j in range(len(A)):
for i in range(S, A[j] - 1, -1):
if F[i -A[j]][0] == 1:
F[i][0] = 1
F[i][1] = A[j]
#print('\n'.join(map(str, F)))
i = S
while F[i][0] == 0:
i -= 1
print(f'Total length = {i}')
ans = []
while i > 0:
ans.append(F[i][1])
i -= F[i][1]
print(f'segments = {ans}')
Вывод:
Total length = 300
segments = [139, 139, 22]
Process finished with exit code 0
Показывает два отрезка по 139 , хотя в списке присутствует только один. Подскажите как исправить.
Ответы (1 шт):
Эта ошибка кочует по Сети. Она есть в видео Занятие 26 Задача об укладке рюкзака и она же есть главе 3. Задача «Золотые слитки» на сайте Информатикс.
Объяснить в чём она состоит не легко. Сам алгоритм верный, ошибается та часть, которая отвечает за восстановление набора предметов в рюкзаке.
Разберём пример A = [1, 2, 3] и S = 6. Алгоритм заполняет двумерный массив F. Первоначально F заполнен почти всеми нулями:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
После обработки первого веса:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
После обработки второго веса:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | |
| 0 | 1 | 2 | 2 | 0 | 0 | 0 |
Пока всё было хорошо. Но третий вес переписывает некоторые ячейки в последней строке. Раньше в F[3][1] была записана двойка, теперь тройка.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 2 | 3 | 3 | 3 | 3 |
Теперь часть алгоритма, которая строит набор весов, построит ответ [3, 3], что, конечно, ошибка.
Простейшее изменение – замена оператора
if F[i -A[j]][0] == 1:
на
if F[i][0] == 0 and F[i -A[j]][0] == 1:
Условие до and защищает данные записанные на предыдущих циклах от изменений в текущем цикле.