Прежде всего, я хотел бы извиниться за мой плохой английский sh.
Я боролся с этим заданием в моем курсе программирования. Я не могу понять, как мне создать список выбора, в котором программа просматривает все возможные комбинации и возвращает наилучшую комбинацию в виде списка.
Для этого упражнения нам необходимо использовать только Шаблон кода нам дали. Импорт библиотек или команд и т.п. не допускается. Добавление параметров к рассматриваемой функции недопустимо
Я перевел комментарии и задания с моего родного языка на английский sh, поэтому извините, если что-то не совсем понятно.
Назначение / объяснение алгоритма, который мы должны кодировать, следующее:
- Рассчитать вес и значение текущего выбора
- , если общее вес превышает максимальный вес:
- else:
- устанавливает текущий выбор как лучший выбор
- повторите для каждого объекта, который еще не появился в выделении
- добавьте объект к текущему выделению и рекурсивно вызовите функцию для этого выделения
- , если поиск даст лучшее решение
- сохранить выбор как лучший выбор
- , затем удалить объект из текущего выбора
- вернуть наилучший выбор
Это шаблон кода, который нам дали:
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)
Я знаю мой код абсолютно ужасен и я очень не спрашиваю для кого-то, чтобы просто дать мне весь код и в основном выполнить задание для меня. Я просто не могу обдумать, как я должен создать этот алгоритм и как обойти эту проблему, которую я объяснил в начале.