Блог

Для домашнего задания по алгоритму меня просят дать решение проблемы с рюкзаком. У меня есть на входе список продуктов. Продукту присваивается стоимость и количество калорий. Итак, у меня есть два набора, один из денег и один из ккал. Моя цель-выбрать продукты, которые дают равную сумму денег и ккал.

например, если у меня есть этот ввод: (1, 3), (2, 4), (5, 8), (4, 5)

и денежная сумма, равная m=7, и сумма ккал, равная k=12, мне нужно выбрать продукты, которые точно удовлетворяют двум суммам. В моем примере я выберу продукты (2, 4) и (5, 8). Мое решение должно возвращать значение true только в том случае, если существуют продукты, соответствующие требованиям, в противном случае возвращайте значение false. Нет необходимости возвращать набор продуктов

Я уже написал решение с использованием рекурсии на основе проблемы подмножеств, в котором я вспоминаю, использовала ли моя функция последний продукт или нет. Это решение работает, но оно слишком медленное -gt; 2^n.

 def isSubsetSum(set, n, sum, set2, sum2):  if (sum == 0 and sum2==0):  return True  if (n == 0 or (sum lt; 0 or sum2 lt; 0)):  return False    if (set[n] gt; sum) or (set2[n] gt; sum2): # if one of the two values (money, calories) is bigger than the sum   return isSubsetSum(set, n-1, sum, set2, sum2) # we avoid using this product -gt; recall with n-1   inclusion = isSubsetSum(set, n-1, sum-set[n], set2, sum2-set2[n]) # we recurse includig the last product  exclusion = isSubsetSum(set, n-1, sum, set2, sum2) # we recurse excluding the last product  return inclusion or exclusion  

Я попытался изменить свою функцию подмножества на подход динамического программирования, но у меня возникли трудности с изменением моей функции для работы с двумя наборами (набор денег и набор калорий).

Я поговорил с ассистентами преподавателя, и они сориентировали меня в выборе проблемы рюкзака вместо проблемы суммы подмножеств. Я видел, как работает подход динамического программирования ранца, но у меня те же проблемы, что и раньше, с подмножествами, при изменении задачи для работы с моими входными данными.

Я думаю, что я что-то упускаю, было бы здорово, если бы вы помогли мне понять, где я ошибаюсь.

Спасибо

Вот как может выглядеть подход динамического программирования:

 import numpy as np  M = 7  K = 12 products = [(1, 3), (2, 4), (5, 8), (4, 5)]  # For an empty list of products, only the problem with m=k=0 is solvable: solvable = np.zeros(shape=(M   1, K   1), dtype=bool) solvable[0, 0] = True  def one_more(product, solvable):  result = solvable.copy()  m_inc, k_inc = product  for m in range(m_inc, M   1):  for k in range(k_inc, K   1):  if not solvable[m, k]:  result[m, k] = solvable[m - m_inc, k - k_inc]  return result  for product in products:  solvable = one_more(product, solvable)  # The full problem of interest: print(solvable[M, K])  

NumPy полезен здесь, поскольку он обеспечивает двумерную структуру данных массива, но вы можете добиться того же эффекта с вложенными списками.

Мы начинаем с целевых значений M и K в качестве констант и заданного списка продуктов. Ключевая идея состоит в том, чтобы перебирать список продуктов, начиная с 0 продуктов и добавляя по одному продукту за раз, каждый раз обновляя матрицу ( solvable ), которая указывает, какие подзадачи разрешимы для данного частичного списка проблем.

Более конкретно, solvable[i, j] это верно, если проблема с m=i и k=j разрешима с текущим неполным списком продуктов.

Функция one_more() обновляет solvable матрицу для добавления еще одного доступного продукта. Подзадачи, которые не были разрешимы без этого нового продукта, становятся разрешимыми, если подзадача с m и k, уменьшенными на значения нового продукта, уже разрешима.

Как только мы обновим solvable все продукты, мы сможем найти интересное решение в правом нижнем углу этой матрицы.