Это сценарий:
B1, B2, B3, B4, B5, B6 - блоки
S1, S2, S3 - слоты
Каждый блок может бытьположить в определенные слоты.
т.е. B1 = ["S1", "S2", "S3"].В эти 3 слота можно вставить средства B1.
B2 = [S1, S2]
B3 = [S3]
Вы можете сделать продукт, взяв один блокиз каждого слота -
, т. е. рецепт для продукта (1 из S1) + (1 из S2) + (1 из S3)
Нужна функция / алгоритм для размещения этих блоковв каждом слоте сделать максимальное количество продуктов.
В данном примере - 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