排序算法理念

Question

我想为一个特定的游戏库存创建一个排序算法。

每个物品都有一个ID和一个大小（1-3）。大小反映了它在库存中占据了多少槽位，垂直方向。

我想主要利用它的大小来创建一个排序算法，所以最大的物品放在第一位，这样就很简单了。然而库存有多页，每页有5列10行。这就是问题出现的地方。从逻辑上讲，你会用3个大小的物品填满第一个清单，然而这意味着在最后一行不会有任何物品。所以算法必须将前6行填满3个尺寸的物品，后4行填满2个尺寸的物品。项目的数量是动态的，所以不一定每次都是这样。谁能给我指点一下？我使用的是python。非常感谢您

Answer 1

如果你的目标是

• 尽量减少未被占用的行数
• 然后在等量齐观的情况下，优先选择 "大件 "最多的那一个。

你可以采用0-1节算法：最大限度地提高 "成本"，最高可达10。

下面是根据之前的解决方案笨拙地复制粘贴和改编的。我的回答

长话短说。

• 应用knapsack（自己做，代码只是为了说明）。
• 候选品
• 在下面的实现中，我们将候选人的大小增加，使其大小相等的情况下，其大小越小的项目越大（满足我们的要求）。
• 如果没有人达到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) 我们可以通过在前面加上 values=sorted(values, reverse=True) 在开始的时候。

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