我有一个包含物品的商店。每个项目要么是一个组件（原子），要么是由各种组件组成的产品（但绝不是两个或多个相同的组件）。
现在，当我想将产品从商店中取出时，有多种情况：
- 商店包含产品的必要数量。
- 该商店包含我可以组装产品的组件。
- 商店包含与所需产品共享组件的产品。我可以拆卸它们并组装所需的物品。
- 以上任意组合。
到目前为止，您可以在下面看到我的代码（getAssemblyPath）。如果可能的话，它确实找到了组装所需项目的方法，但它并没有优化组装路径。
我想通过两种方式优化路径：
- 首先，选择组装/反汇编操作次数最少的路径。
- 其次，如果有多种这样的路径，请选择在商店中留下最少数量的拆卸组件的路径。
现在，在这里，我完全不知道如何完成此优化（我什至不确定这是针对 SO 还是针对数学的问题）。
如何进行更改getAssemblyPath以使其满足我的优化要求？
到目前为止我的代码：
#! /usr/bin/python
class Component:
def __init__ (self, name): self.__name = name
def __repr__ (self): return 'Component {}'.format (self.__name)
class Product:
def __init__ (self, name, components):
self.__name = name
self.__components = components
@property
def components (self): return self.__components
def __repr__ (self): return 'Product {}'.format (self.__name)
class Store:
def __init__ (self): self.__items = {}
def __iadd__ (self, item):
item, count = item
if not item in self.__items: self.__items [item] = 0
self.__items [item] += count
return self
@property
def items (self): return (item for item in self.__items.items () )
@property
def products (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Product) )
@property
def components (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Component) )
def getAssemblyPath (self, product, count):
if product in self.__items:
take = min (count, self.__items [product] )
print ('Take {} of {}'.format (take, product) )
count -= take
if not count: return
components = dict ( (comp, count) for comp in product.components)
for comp, count in self.components:
if comp not in components: continue
take = min (count, components [comp] )
print ('Take {} of {}'.format (take, comp) )
components [comp] -= take
if not components [comp]: del components [comp]
if not components: return
for prod, count in self.products:
if prod == product: continue
shared = set (prod.components) & set (components.keys () )
dis = min (max (components [comp] for comp in shared), count)
print ('Disassemble {} of {}.'.format (dis, prod) )
for comp in shared:
print ('Take {} of {}.'.format (dis, comp) )
components [comp] -= take
if not components [comp]: del components [comp]
if not components: return
print ('Missing components:')
for comp, count in components.items ():
print ('{} of {}.'.format (count, comp) )
c1 = Component ('alpha')
c2 = Component ('bravo')
c3 = Component ('charlie')
c4 = Component ('delta')
p1 = Product ('A', [c1, c2] )
p2 = Product ('B', [c1, c2, c3] )
p3 = Product ('C', [c1, c3, c4] )
store = Store ()
store += (c2, 100)
store += (c4, 100)
store += (p1, 100)
store += (p2, 100)
store += (p3, 10)
store.getAssemblyPath (p3, 20)
这输出：
Take 10 of Product C
Take 10 of Component delta
Disassemble 10 of Product A.
Take 10 of Component alpha.
Disassemble 10 of Product B.
Take 10 of Component charlie.
这可行，但它确实不必要地拆卸产品 A，因为产品 B 包含所需的组件 alpha 和 charlie。
--
编辑：
回答 Blckknght 的非常明智的问题：
当您说您想要“最少数量的组装/拆卸操作”时，您是指最少数量的项目，还是最少数量的不同产品？
“asm/disasm 动作”是组装或拆卸一个产品的动作，无论涉及多少组件。我正在寻找最少数量的触摸项目，无论它们是否不同。
也就是说，拆掉产品 A 的 20 个比拆掉产品 A 的 10 个和额外的产品 B 的 5 个更好吗？
后者更接近最优。
此外，您说您希望避免留下许多组件，但在您当前的代码中，所有未由请求的产品使用的反汇编组件都将丢失。这是故意的（也就是说，你想扔掉其他组件），还是一个错误？
该方法getAssemblyPath仅确定如何获取项目的路径。它不接触实际的商店。它在任何时候都不会分配给self.__items。将其视为向商店发出订单的功能，以保留他在（近期）将来必须做的事情，以便从他的商店中取出所需数量的所需物品。
--
编辑2：
解决这个问题的第一个明显（或至少对我来说是显而易见的）方法是首先搜索那些与所需产品共享最大数量的组件的产品，因为每次拆卸都会获得更多所需的组件。但不幸的是，这并不一定会产生最佳路径。举个例子：
产品 A 由组分 α、β、γ、δ、ε 和 ζ 组成。
产品 B 由成分 α、β、η、δ、ε 和 θ 组成。
产品 C 由组分 α、β、γ、ι、κ 和 λ 组成。
产品 D 由分量 μ、ν、ξ、δ、ε 和 ζ 组成。
我们有 A 的 0 个，B 的 100 个，C 的 100 个和 D 的 100 个。我们需要 A 的 10 个。现在如果我们首先寻找与 A 共享大多数组件的产品，我们会找到 B。我们拆卸 10 个B 得到 10 个 α、β、δ 和 ε。但是我们需要拆解 C 的 10 个（得到 γ）和 D 的 10 个（得到 ζ）。这将是 40 个动作（30 个拆卸和 10 个组装）。但最好的方法是拆卸 10 个 C 和 10 个 D（30 个动作，20 个拆卸和 10 个组装）。
--
编辑 3：
您无需发布 python 代码即可赢得赏金。只需向我解释该算法并证明它确实会产生最佳路径，或者如果存在多个最佳路径之一。