Ранец Backtracking с 1 параметром
Прежде всего, я хотел бы извиниться за свой плохой английский.
Я боролся с этим заданием в моем курсе программирования. Я не могу понять, как мне создать список выбора, в котором программа перебирает все возможные комбинации и возвращает лучшую комбинацию в виде списка.
Для этого упражнения от нас требуется использовать только предоставленный нам шаблон кода. Импорт библиотек, команд и т.п. запрещен. Добавление параметров к рассматриваемой функции не допускается.
Я перевел комментарии и задания со своего родного языка на английский, так что извините, если что-то не совсем понятно.
Назначение / объяснение алгоритма, который мы должны закодировать, следующее:
- Рассчитать вес и стоимость текущего выбора
- если общий вес превышает максимальный:
- вернуть пустой список
- еще:
- установить текущий выбор как лучший выбор
- повторить для каждого объекта, который еще не появился в выделении
- добавить объект в текущий выбор и рекурсивно вызвать функцию для этого выбора
- если поиск дает лучшее решение
- сохранить выбор как лучший выбор
- затем удалите объект из текущего выделения
- вернуть наилучший возможный выбор
Это шаблон кода, который нам дали:
weights = [50, 50, 60, 80, 100, 110, 120, 150, 150, 200]
values = [80, 80, 60, 50, 100, 90, 100, 170, 200, 240]
# number of objects
numberobjects = len(weights)
# Max weight
max_weight = 320
# Calculates the total weight of a selection of objects and returns it
# The parameter selection is a list, which contains the numbers of the selected
# objects (the objects have the numbers 0 to number - 1, in which number is the total
# number of objects. Every number can only appear once in the selection. This, however, isn't
# checked here!
def calculate_weight(selection):
totalweight = 0
for i in selection:
totalweight = totalweight + weights[i]
return totalweight
# Calculates the total value of a selection of objects and returns it
def calculate_value(selection):
totalvalue = 0
for i in selection:
totalvalue = totalvalue + values[i]
return totalvalue
# Returns all objects, that don't appear in the selection
# The result is a list of numbers from 0 to number - 1 which don't appear in the list 'selection'
# (sorted in ascending order)
def missing_objects(selection):
found = []
for i in range(0, numberobjects):
found = found + [False]
for i in selection:
found[i] = True
numbers = []
for i in range(0, anzahl):
if not found[i]:
numbers = numbers + [i]
return numbers
# Implements the Backtracking Search.
# Expects the current selection as parameter
# Returns the best possible selection list as a result
# or the empty list, if the current selection list already exceeds the maximum weight
# In the beginning the function is started with an empty list as a paremeter
def find_selection(current_selection):
return [] # TODO: Replace with correct code!
# Start search
result = find_selection([])
# Print the selection found and its total weight and value
print("Best Selection: " + str(result))
print("Total Weight: " + str(calculate_weight(result)))
print("Total Value: " + str(calculate_value(result)))
Вот что у меня есть на данный момент:
weights = [50, 50, 60, 80, 100, 110, 120, 150, 150, 200]
values = [80, 80, 60, 50, 100, 90, 100, 170, 200, 240]
# number of objects
numberobjects = len(weights)
# Max weight
max_weight = 320
# Calculates the total weight of a selection of objects and returns it
# The parameter selection is a list, which contains the numbers of the selected
# objects (the objects have the numbers 0 to number - 1, in which number is the total
# number of objects. Every number can only appear once in the selection. This, however, isn't
# checked here!
def calculate_weight(selection):
totalweight = 0
for i in selection:
totalweight = totalweight + weights[i]
return totalweight
# Calculates the total value of a selection of objects and returns it
def calculate_value(selection):
totalvalue = 0
for i in selection:
totalvalue = totalvalue + values[i]
return totalvalue
# Returns all objects, that don't appear in the selection
# The result is a list of numbers from 0 to number - 1, which don't appear in the list 'selection'
# (sorted in ascending order)
def missing_objects(selection):
found = []
for i in range(0, numberobjects):
found = found + [False]
for i in selection:
found[i] = True
numbers = []
for i in range(0, anzahl):
if not found[i]:
numbers = numbers + [i]
return numbers
# Implements the Backtracking Search.
# Expects the current selection as parameter
# Returns the best possible selection list as a result
# or the empty list, if the current selection list already exceeds the maximum weight
# In the beginning the function is started with an empty list as a paremeter
def find_selection(n):
#calculate totals
pos = 0
res = []
totalvalue = 0
totalweight = 0
calculate_weight(res)
calculate_value(res)
#case : return empty list if overweight
if totalweight > max_weight:
return []
else:
res.append(pos)
pos += 1
find_selection(res)
print(res)
test = find_selection([])
print(test)
Я знаю, что мой код абсолютно ужасен, и я очень не прошу кого-то просто дать мне весь код и в основном выполнить задание за меня. Я просто не могу понять, как я должен создать этот алгоритм и как я могу решить эту проблему, которую я объяснил в начале.