Алгоритм сортировки Идея

Question

Я хочу создать алгоритм сортировки для определенного c инвентаря игры.

Каждый предмет имеет идентификатор и размер (1-3). Размер отражает, сколько слотов он занимает в инвентаре, по вертикали.

Я хочу создать алгоритм сортировки, используя его размер в основном так, чтобы самые большие элементы были первыми, и это было бы очень просто. Однако инвентарь имеет несколько страниц, каждая страница имеет 5 столбцов по 10 строк. Это где проблема появляется. По логике вещей вы будете заполнять первый инвентарь 3-мя предметами, однако это означает, что в последнем ряду не будет никаких предметов. Таким образом, алгоритм должен заполнить первые 6 строк тремя элементами размера, а вторые 4 - двумя элементами размера. Количество предметов является динамическим c, так что это может быть не каждый раз. Может кто-то указать мне верное направление? Я использую python. Большое спасибо!

Answer 1

Если ваша цель:

• свести к минимуму количество незанятых строк
• , то при эквивалентном решении предпочтите тот, в котором больше всего "больших предметов"

Вы можете применить алгоритм ранца 0-1: максимизировать «стоимость» до 10

Ниже решения тупо скопировать и адаптировать из моего предыдущего ответа

Короче говоря:

• применить рюкзак (сделай сам, код только для иллюстрации)
• кандидат - это набор предметов, выбранных среди всех доступных items
• в разделе ниже, мы увеличиваем размер кандидата, поэтому при равной сумме, чем меньше его размер, тем больше элементов в нем (что соответствует нашему требованию)
• по умолчанию для кандидата, чья сумма равна ближайший к 10, если ни один не достигает 10 (best_fallback)

from collections import namedtuple
def pick_items (values):
  S = 10
  Candidate = namedtuple('Candidate', ['sum', 'lastIndex', 'path'])
  tuples = [Candidate(0, -1, [])]

  best_fallback = tuples[0]
  while len(tuples):
    next = []
    for (sum, i, path) in tuples:
      for j in range(i + 1, len(values)):
        v = values[j]
        if v + sum <= S:
          candidate = Candidate(sum = v + sum, lastIndex = j, path = path + [v])
          if candidate[0] > best_fallback[0]:
            best_fallback = candidate
          next.append(candidate)
          if v + sum == S:
            return path + [v]
    tuples = next
  return best_fallback[2]

print(pick_items([3,3,3,1])) #finds the trivial sum [3, 3, 3, 1]
print(pick_items([1,3,3,1])) #returns the closest to goal [1, 3, 3, 1]
print(pick_items([2,2,2,2,2,1,3,3,1])) #returns the shortest set [2, 2, 3, 3]
print(pick_items([3,3,2,2,3])) #returns an exact count [3, 3, 2, 2]
print(pick_items([3,1,1,1,2,2,2,2])) #shortest set as well [3, 1, 2, 2, 2]

PS: относительно набора [2,2,2,2,2,3,1,3,1] (где есть два решения одинакового размера: (3,1, 3,1, 2) и (2,2, 2,2 ,2), мы можем заставить порядок, в котором решения исследуются с помощью префикса * 10 31 * в начале:

def pick_items (values):
  # force biggest items solution to be explored first
  values = sorted(values, reverse=True)
  S = 10