这是场景：
B1、B2、B3、B4、B5、B6 是块
S1、S2、S3 是插槽
每个块都可以放入特定的插槽中。
即， B1 = ["S1","S2", "S3"] 。可以将装置 B1 放入这 3 个插槽中。
B2 = [S1，S2]
B3 = [S3]
您可以通过从每个插槽中取出一个块来制作产品 -
即，产品的配方是（来自 S1 的 1）+（来自 S2 的 1）+（来自 S3 的 1）
需要一个函数/算法将这些块放在每个插槽中以制造最大数量的产品。
在给定的示例中 - B3 将在 S3 中，因为 B3 只允许放入该插槽中。但是，虽然 B1 可以放在任意 3 个插槽中，但我们应该放在 S1 中，因为要制作设备，我们需要 S1 + S2 + S3 并且 B3 只能放在 S3 中。所以在插槽之间分配块的最佳方式是：B1-> S1, B2 -> S2, B3 -> S3
所以我们可以按照配方制作一种产品，即（1 来自 S1 + 1 来自 S2 +1 来自 S3 ）
Example Input
============
block_slots = {
"BLOCK1" : ["SLOT - 1","SLOT - 3", "SLOT - 2"],
"BLOCK2" : ["SLOT - 1","SLOT - 3"],
"BLOCK3" : ["SLOT - 1","SLOT - 3", "SLOT - 2"],
"BLOCK4" : ["SLOT - 1","SLOT - 2"],
"BLOCK5" : ["SLOT - 3", "SLOT - 2"],
"BLOCK6" : ["SLOT - 1","SLOT - 3", "SLOT - 2"],
"BLOCK7" : ["SLOT - 1","SLOT - 3", "SLOT - 2"],
"BLOCK8" : ["SLOT - 1","SLOT - 3", "SLOT - 2"],
"BLOCK9" : ["SLOT - 3", "SLOT - 2"],
"BLOCK10" : ["SLOT - 3", "SLOT - 2"],
"BLOCK11" : ["SLOT - 1"],
"BLOCK12" : ["SLOT - 2"],
}
Output
==========
{
"BLOCK8": "SLOT - 1",
"BLOCK9": "SLOT - 3",
"BLOCK2": "SLOT - 1",
"BLOCK3": "SLOT - 2",
"BLOCK1": "SLOT - 3",
"BLOCK6": "SLOT - 2",
"BLOCK7": "SLOT - 1",
"BLOCK4": "SLOT - 2",
"BLOCK5": "SLOT - 3",
"BLOCK10": "SLOT - 3",
"BLOCK11": "SLOT - 1",
"BLOCK12": "SLOT - 2"
}
> 4 Blocks in each slot. 4 Products can be made from 12 blocks which is
> maximum yield.
我尝试了以下代码：
blocks = {
"B1" : ["S1","S3", "S2"],
"B2" : ["S1","S3"],
"B3" : ["S1","S3", "S2"],
"B4" : ["S1","S2"],
"B5" : ["S3", "S2"],
"B6" : ["S1","S3", "S2"],
"B7" : ["S1","S3", "S2"],
"B8" : ["S1","S3", "S2"],
"B9" : ["S3", "S2"]
}
slot_count = {}
block_slot_final = {}
for block,block_slots in blocks.iteritems():
for slot in block_slots:
if slot in slot_count:
slot_count[slot] = slot_count[slot] + 1
else:
slot_count[slot] = 0
blocks_sorted = sorted(blocks.items(), key=lambda items: len(items))
for block,slots in blocks_sorted:
final_slot = slots[0]
for slot in slots:
if slot_count[slot] < slot_count[final_slot]:
final_slot = slot
block_slot_final[block] = final_slot
print block_slot_final
它给出了这个输出
{'B4'：'S1'，'B5'：'S3'，'B6'：'S1'，'B7'：'S1'，'B1'：'S1'，'B2'：'S1'，' B3'：'S1'，'B8'：'S1'，'B9'：'S3'}
有了这个，我们无法制造任何产品，因为 S2 中没有块。
尝试了另一种更好但仍不完美的解决方案。下面是代码。它给出了这个输出：
{'B4'：'S1'，'B5'：'S3'，'B6'：'S2'，'B7'：'S1'，'B1'：'S3'，'B2'：'S1'，' B3'：'S2'，'B8'：'S3'，'B9'：'S2'}
def get_least_consumed_slot(block_slot,slots):
least_consumed_slot = slots[0]
for slot in slots:
if slot_block_count[slot] < slot_block_count[least_consumed_slot]:
least_consumed_slot = slot
return least_consumed_slot
blocks = {
"B1" : ["S1","S3", "S2"],
"B2" : ["S1","S3"],
"B3" : ["S1","S3", "S2"],
"B4" : ["S1","S2"],
"B5" : ["S3", "S2"],
"B6" : ["S1","S3", "S2"],
"B7" : ["S1","S3", "S2"],
"B8" : ["S1","S3", "S2"],
"B9" : ["S3", "S2"]
}
slot_occurance_count = {}
block_slot_final = {}
all_slots = []
slot_block_count = {}
for block,block_slots in blocks.iteritems():
for slot in block_slots:
if slot not in all_slots:
all_slots.append(slot)
slot_block_count[slot] = 0
if slot in slot_occurance_count:
slot_occurance_count[slot] = slot_occurance_count[slot] + 1
else:
slot_occurance_count[slot] = 1
blocks_sorted = sorted(blocks.items(), key=lambda items: len(items))
for block,slots in blocks_sorted:
# final_slot = slots[0]
# for slot in slots:
# if slot_occurance_count[slot] < slot_occurance_count[final_slot]:
# final_slot = slot
# block_slot_final[block] = final_slot
least_consumed_slot = get_least_consumed_slot(block_slot_final,slots)
block_slot_final[block] = least_consumed_slot
slot_block_count[least_consumed_slot] = slot_block_count[least_consumed_slot] + 1
print block_slot_final