Проблема с рюкзаком: заменяет все предметы ценными - PullRequest
Новая
       15

Проблема с рюкзаком: заменяет все предметы ценными

0 голосов
/ 29 сентября 2019

Я пытаюсь решить проблему с рюкзаком, применяя свой собственный алгоритм.Я даю каждому предмету очки (значения [i] - веса [i]) и добавляю предметы с высокими показателями в свой рюкзакНо этот код заменяет каждый элемент первым элементом со значениями (5). 

def knapsack(weights, values, capacity):
  knapsack = []
  scores = []
  for i in range(len(values)):
    score = values[i] - weights[i]
    scores.append(score)
  weight = 0
  while weight < capacity:
    if len(scores) != 0:
      valuable = max(scores)
      knapsack.append(values[scores.index(valuable)])
      weight += weights[scores.index(valuable)]
      scores.pop(scores.index(valuable))
    else:
      break
  return knapsack

weights = [1, 2, 4, 2, 5]
values  = [5, 3, 5, 3, 2]
capacity = 10

print(knapsack(weights, values, capacity))

Что не так с этим кодом?

Редактировать: Эй, ребята, я исправил это, но, похоже,быть логической ошибкойЕсли: 

weights = [8, 2,  6,  7, 9]
values  = [3, 11, 13, 7, 4]
capacity = 24

Тогда есть два предмета с одинаковым счетом (8, 3 и 9, 4), но 9, 4 лучше, поскольку он точно вписывается в рюкзак и имеет более высокое значение.Даже изменение строки 8 на <= не помогает. </p>

Ответы [ 2 ]

0 голосов
/ 29 сентября 2019

Оценки для этого набора данных оказываются в порядке убывания, поэтому индекс самого ценного элемента всегда равен индексу 0, когда вы убираете оценки из списка.Поскольку вы также не выталкиваете значения из начального списка, когда добавляете их в свой рюкзак, вы всегда добавляете 0-й элемент в рюкзак.

При удалении извлекайте значение из исходного спискаиз рюкзака, и он добавит все значения по порядку. 

knapsack.append(values.pop(scores.index(valuable)))

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

0 голосов
/ 29 сентября 2019

Вы также не удаляете добавленные значения из списка.Попробуйте добавить 

values.pop(scores.index(valuable))
weights.pop(scores.index(valuable))

в строку до scores.pop(...).

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

if (weight + weights[scores.index(valuable)]) > capacity:
    break

Вам нужен код для работы с тай-брейками, который переназначает индекс очков на предмет с наивысшей ценностью, который подходит под емкость, например: 

ties = [i for i, x in enumerate(scores) if x == valuable]
if len(ties) > 1:
    most_valuable = -1
    for idx in ties:
        if values[idx] > most_valuable and (weight + weights[idx]) <= capacity:
            most_valuable = values[idx]
            scores_idx = idx

Полный код: 

def knapsack(weights, values, capacity):
    knapsack = []
    scores = []
    for i in range(len(values)):
        score = values[i] - weights[i]
        scores.append(score)
    weight = 0
    while weight < capacity:
        if len(scores) != 0:
            valuable = max(scores)
            scores_idx = scores.index(valuable)
            ties = [i for i, x in enumerate(scores) if x == valuable]
            if len(ties) > 1:
                most_valuable = -1
                for idx in ties:
                    if values[idx] > most_valuable and (weight + weights[idx]) <= capacity:
                        most_valuable = values[idx]
                        scores_idx = idx
            if (weight + weights[scores_idx]) > capacity:
                break
            knapsack.append(values[scores_idx])
            weight += weights[scores_idx]
            values.pop(scores_idx)
            weights.pop(scores_idx)
            scores.pop(scores_idx)
        else:
            break
    return knapsack

#  weights = [1, 2, 4, 2, 5]
#  values  = [5, 3, 5, 3, 2]
#  capacity = 10
weights = [8, 2, 6, 7, 9]
values = [3, 11, 13, 7, 4]
capacity = 24

print(knapsack(weights, values, capacity))
...