python - 获得最大 yield 的算法

Question

这是场景:

B1、B2、B3、B4、B5、B6是 block

S1、S2、S3 是槽

每个 block 都可以放入特定的槽中。

即 B1 = ["S1","S2", "S3"] 。表示B1可以放入这3个槽位。

B2 = [S1, S2]

B3 = [S3]

您可以通过从每个插槽中取出一个 block 来制作产品 -

也就是说，产品的配方是(1个来自S1)+(1个来自S2)+(1个来自S3)

需要一个函数/算法来将这些 block 放入每个槽中以制造最大数量的产品。

在给定的示例中 - B3 将在 S3 中，因为 B3 只能放入该插槽。然而，虽然 B1 可以放在任何 3 个插槽中，但我们应该放在 S1 中，因为要制作设备，我们需要 S1 + S2 + S3，而 B3 只能放在 S3 中。所以在槽之间分配 block 的最佳方式是: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 中没有区 block 。

---

尝试了另一种更好但仍不完美的解决方案。下面是代码。它给出了这个输出:

{'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

Answer 1

有待澄清，这是枚举所有最大匹配 (1) 或找到一个最大匹配 (2) 的问题。

(1) 枚举所有完美、最大和二分图中的最大匹配宇野武明 http://research.nii.ac.jp/~uno/papers/isaac97web.pdf

(2) 例如，Hopcroft--Karp https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm