CODEWITHSUNDEEP
pythonalgorithmsortingmath
George Johnson
George Johnson

Reputation: 41

Sorting Algorithm Idea

I want to create a sorting algorithm for a specific game inventory.

Each item has an ID and a size (1-3). The size reflects how many slots it occupies in the inventory, vertically.

I want to create a sorting algorithm using its size mainly so the largest items are first and that would be very simple. However the inventory has multiple pages, each page having 5 columns of 10 rows. This is where the problem appears. Logically you will fill up the first inventory with 3 sized items, however that means that in the last row there wont be any items. So the algorithm has to fill the first 6 rows with 3 size items, and the second 4 with 2 size items. The number of items is dynamic so that may not be the case every time. Can anyone point me in the right direction? I am using python. Thank you very much!

Upvotes: 2

Views: 101

Answers (1)

grodzi
grodzi

Reputation: 5703

If your goal is to:

  • minimize the number of unoccupied rows
  • then at equivalent solution, prefer the one which has the most "big items"

You may apply a 0-1 knapsack algorithm: maximize the "cost" up to 10

Below a solution dumbly copy-pasted and adaptated from a previous answer of mine

long story short:

  • apply knapsack (do it yourself, code is just for illustration)
  • a candidate is a set of items picked among all the available items
  • in implem below, we grow the candidate size so at equal sum, the shorter its size the bigger the items in it (which fulfills our requirement)
  • default to the candidate whose sum is closest to 10 if none reach 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: regarding the set [2,2,2,2,2,3,1,3,1] (where there are two solutions of equal size: (3,1, 3,1, 2) and (2,2, 2,2 ,2) we may force the order in which the solutions are explored by prefixing values=sorted(values, reverse=True) at the begininning:

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

Upvotes: 1

Related Questions