基于标准的项目分组

Question

我有一个项目清单：

ShelvesToPack = [{'ShelfLength': 2278.0, 'ShelfWidth': 356.0, 'ShelfArea': 759152.0, 'ItemNames': 1},
{'ShelfLength': 1220.0, 'ShelfWidth': 610.0, 'ShelfArea': 372100.0, 'ItemNames': 2},
{'ShelfLength': 2310.0, 'ShelfWidth': 762.0, 'ShelfArea': 1760220.0, 'ItemNames': 3},
{'ShelfLength': 610.0, 'ShelfWidth': 610.0, 'ShelfArea': 1450435.0, 'ItemNames': 4}]

我需要一个程序，告诉多少最小数量的组一个人可以有和项目如何分组。你知道吗

我想对这些项目进行分组，使项目的搁置长度之和<；=最大长度或项目搁置宽度之和<；=最大宽度和项目搁置面积之和<；=最大面积。在这种情况下，如果我们看一下逻辑，我们可以将所有项目打包成至少两组-项目1和3将形成一组，项目2和4将形成另一组。我想得到以下格式的答案：

[[{'ShelfLength': 2278.0, 'ShelfWidth': 356.0, 'ShelfArea': 759152.0, 'ItemNames': 1} ,
 {'ShelfLength': 2310.0, 'ShelfWidth': 762.0, 'ShelfArea': 1760220.0, 'ItemNames': 3}],
[{'ShelfLength': 1220.0, 'ShelfWidth': 610.0, 'ShelfArea': 372100.0, 'ItemNames': 2},
 , {'ShelfLength': 610.0, 'ShelfWidth': 610.0, 'ShelfArea': 1450435.0, 'ItemNames': 4}]]

我已经写了一个代码，但它没有给我想要的结果。你知道吗

ShelvesToPack_sorted = sorted(ShelvesToPack, key = itemgetter('ShelfWidth'), reverse = True)
AreaOfObject = 2972897.28
current_width = 0
current_length = 0
current_area = 0
ply =[]
plywoods=[]
for item in ShelvesToPack_sorted:
    if (current_width + item['ShelfWidth'] <= 1219.2  or  current_length + item['ShelfLength'] <= 2438.5) and  current_area + item['ShelfArea'] <= AreaOfObject:
        ply.append(item)
        current_width += item['ShelfWidth']
        current_length += item['ShelfLength']
        current_area += item['ShelfArea']
    else:
       plywoods.append(ply)
       if (item['ShelfWidth'] <= 1219.2  or item['ShelfLength'] <= 2438.5) and item['ShelfArea'] <= AreaOfObject:
           ply = [item]
           current_width = item['ShelfWidth']
           current_length = item['ShelfLength']
           current_area = item['ShelfArea']
       else:
           ply = []
           current_width = 0
           current_length = 0
           current_area = 0

if ply:
    plywoods.append(ply)

print(plywoods)

我得到了以下输出，这是不太正确，我不能做正确的分组。你知道吗

[[{'ItemNames': 3, 'ShelfWidth': 762.0, 'ShelfLength': 310.0, 'ShelfArea': 1760220.0}],
 [{'ItemNames': 2, 'ShelfWidth': 610.0, 'ShelfLength': 1220.0, 'ShelfArea': 372100.0},
  {'ItemNames': 4, 'ShelfWidth': 610.0, 'ShelfLength': 610.0, 'ShelfArea': 1450435.0}],
 [{'ItemNames': 1, 'ShelfWidth': 356.0, 'ShelfLength': 2278.0, 'ShelfArea': 759152.0}]]

有人能建议一下吗？你知道吗

Answer 1

这里有一些似乎工作正常的东西。由于组合中的书架顺序无关紧要，所以它只是使用蛮力方法来检查书架的每个可能组合。因为要处理的代码可能非常多，所以编写效率相当高的代码非常重要。在本质上是一个搜索或路径发现问题的情况下，可能有更多的优化算法可以更快地实现这一点。你知道吗

考虑到这一点，并且为了使访问每个shelf dictionary中的字段更容易，它首先将它们全部转换为代码从此开始使用的namedtuple实例的等效列表。（如果您真的需要词典形式的文档，可以很简单地保留一份副本，或者在必要时重新创建。）

转换完成后，它将检查从1到所有货架项目的所有组合。它将找到的这些存储在名为groups的列表中。group[N]将包含满足条件的N项组合的子列表。（当然，子列表的长度是找到的书架数量的组合数）。你知道吗

例如，在下面的输出中，它显示有4组2个项目符合标准。（不过，它不会打印它们的每个组合。）

from collections import namedtuple
from itertools import combinations
from operator import itemgetter

shelves_to_pack = [
    {'ShelfLength': 2278.0, 'ShelfWidth': 356.0, 'ShelfArea': 759152.0, 'ItemNames': 1},
    {'ShelfLength': 1220.0, 'ShelfWidth': 610.0, 'ShelfArea': 372100.0, 'ItemNames': 2},
    {'ShelfLength': 2310.0, 'ShelfWidth': 762.0, 'ShelfArea': 1760220.0, 'ItemNames': 3},
    {'ShelfLength': 610.0, 'ShelfWidth': 610.0, 'ShelfArea': 1450435.0, 'ItemNames': 4}]

# convert dict list into a namedtuple list to simplify field access
Shelf = namedtuple('Shelf',
                   'length width area item_names')
shelves = [Shelf(length=shelf['ShelfLength'], width=shelf['ShelfWidth'],
                 area=shelf['ShelfArea'], item_names=shelf['ItemNames'])
            for shelf in shelves_to_pack]

MAX_WIDTH, MAX_LENGTH = 1219.2, 2438.5
MAX_AREA = 2972897.28

def meets_criteria(shelf_combo):
    """ Determine if shelf combination meets criteria. """
    return (sum(shelf.area for shelf in shelf_combo) <= MAX_AREA
            and (sum(shelf.length for shelf in shelf_combo) <= MAX_LENGTH
                 or sum(shelf.width for shelf in shelf_combo) <= MAX_WIDTH))

groups = [[]]  # first group representing zero shelf items is always empty
for num_shelves in range(1, len(shelves)+1):
    groups.append([combo for combo in combinations(shelves, num_shelves)
                      if meets_criteria(combo)])
for i, group in enumerate(groups):
    print('groups of {} items: size {}'.format(i, len(group)))

这是由上述代码和输入数据生成的输出：

groups of 0 items: size 0
groups of 1 items: size 4
groups of 2 items: size 4
groups of 3 items: size 0
groups of 4 items: size 0

Answer 2

以下是代码的简化版本：

data = [{'ShelfLength': 2278.0, 'ShelfWidth': 356.0, 'ShelfArea': 759152.0, 'ItemNames': 1},
    {'ShelfLength': 1220.0, 'ShelfWidth': 610.0, 'ShelfArea':   372100.0, 'ItemNames': 2},
    {'ShelfLength': 2310.0, 'ShelfWidth': 762.0, 'ShelfArea': 1760220.0, 'ItemNames': 3},
    {'ShelfLength': 610.0, 'ShelfWidth': 610.0,   'ShelfArea': 1450435.0, 'ItemNames': 4}]
SL = 'ShelfLength'
SW = 'ShelfWidth'
SA = 'ShelfArea'
IN = 'ItemNames'
max_width = 1219.2
max_len = 2438.5
max_area = 2972897.28

grouped_data = [[], []]
for record in data:
    if (record[SL] <= max_len or record[SW] <= max_width) and record[SA] <= max_area:
        grouped_data[0].append(record)
    else:
        grouped_data[1].append(record)

print(grouped_data)

这将得到与您得到的结果相同的结果，这是正确的，因为所有元素都满足您提到的条件。你知道吗