Правка 2: теперь не проходит проверку ({64, 1, 36, 81}, 82)
Правка 1: теперь исправляет проблемы из-за дельты > max(items )
Edit0: теперь обновлено, чтобы исправить бесконечную рекурсию из-за осциллирующей дельта-проблемы.
В этом видео об алгоритмах (около 2:52) профессор Скиена описывает задачу о рюкзаке как следует...
Задача о рюкзаке: при заданном наборе целых чисел S = {s1, s2,..., sN} и целевом числе T найдите подмножество S, которое дает в сумме точно к Т.
Затем он продолжает, что это одна из тех проблем, для которых не существует известного эффективного решения!
Но я все равно пытался, и вот моя попытка решения (и, похоже, это работает для чисел, которые я пробовал)...
from itertools import accumulate
#items - All available items
#target - The size of the knapsack
#returns - A subset of {items} whose sum adds upto target
# if possible else returns None
def KnapsackItems(items, target):
s = sum(items)
if s < target:
return None
delta = s - target
if delta == 0:
return items
if delta in items:
result = items - {delta}
return result
if delta > max(items):
sortedItems = list(sorted(items))
deltas = list(map(lambda x: x - target, accumulate(sortedItems)))
ul = [i for i,d in zip(sortedItems, deltas) if d <= i]
return KnapsackItems(set(ul), target)
else:
U = {i for i in items if i < delta}
V = KnapsackItems(U, delta)
if V:
result = items - V
return result
return None
А вот и тестовый набор...
def test(items, target):
print("Items:", items)
print("Target:", target)
result = KnapsackItems(items, target)
if result and not sum(result) == target:
print("Result:", result)
print("FAIL: sum of returned set does not match target ({})".format(target))
elif result:
print("Result:", result)
print("Success (sum of returned set:{})".format(sum(result)))
else:
print("No solution could be found")
Примеры из видео...
test({1,2,5,9,10}, 22)
test({1,2,5,9,10}, 23) #No solution expected
test({1,2,3,4,5}, 11)
test({1,2}, 2)
test({4,3,2}, 5)
test({1, 3, 4, 7, 9}, 13)
test({6,7,8,3,14,5,15,2,4}, 29)
test({1,2,3,4,5,6,7},14)
test({64, 1, 36, 81}, 82)
Результат...
Items: {9, 10, 2, 5, 1}
Target: 22
Result: {9, 10, 2, 1}
Success (sum of returned set:22)
Items: {9, 10, 2, 5, 1}
Target: 23
No solution could be found
Items: {1, 2, 3, 4, 5}
Target: 11
Result: {1, 2, 3, 5}
Success (sum of returned set:11)
Items: {1, 2}
Target: 2
Result: {2}
Success (sum of returned set:2)
Items: {2, 3, 4}
Target: 5
Result: {2, 3}
Success (sum of returned set:5)
Items: {9, 3, 4, 1, 7}
Target: 13
Result: {9, 4}
Success (sum of returned set:13)
Items: {2, 3, 4, 5, 6, 7, 8, 14, 15}
Target: 29
Result: {14, 15}
Success (sum of returned set:29)
Items: {1, 2, 3, 4, 5, 6, 7}
Target: 14
Result: {2, 5, 7}
Success (sum of returned set:14)
Items: {64, 81, 36, 1}
Target: 82
No solution could be found
Итак, теперь я думаю, вопрос в том, что не так с моим решением проблемы с рюкзаком? Это неэффективно и непригодно для очень больших наборов чисел? Также, пожалуйста, дайте мне знать, если это не то место для таких вопросов.
