我有一个商店，里面有元素。每个项目要么是一个组件(它是原子的)，要么是由各种组件(但绝不是 2 个或更多相同组件)组成的产品。

现在，当我想从商店取货时，有多种情况:

#! /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.

When you say you want "the least number of assembly/disassembly actions", do you mean the smallest number of items, or the smallest number of different products?

That is, is is better to dissassemble 20 of Product A than to dissassemble 10 of Product A and an additional 5 of Product B?

Further, you say you want to avoid leaving many components behind, but in your current code all disassembled components that are not used by the requested Product are lost. Is that deliberate (that is, do you want to be throwing away the other components), or is it a bug?

最佳答案

这是我将如何解决这个问题。我想为此编写代码，但我认为我没有时间。

您可以递归地找到最佳解决方案。制作一个表示零件存储状态和当前请求的数据结构。现在，对于您需要的每个部分，进行一系列递归调用，尝试使用各种方法来填充订单。关键是通过尝试填充订单的方法，您完成了部分工作，因此递归调用现在是同一问题的稍微简单的版本。

这是一个基于您的示例的特定示例。我们需要填写由组件 c1、c3 和 c4 组成的产品 3 (p3) 的订单。我们的订单是 20 个 p3，我们有 10 个 p3 的库存，所以我们随便填写了 p3 的前 10 个订单。现在我们的订单是 p3 的 10，但我们可以将其视为 c1 的 10、c3 的 10 和 c4 的 10 的订单。对于第一次递归调用，我们拆解一个 p1，并为单个 c1 填写订单并在商店中放置一个额外的 c2；所以这个递归调用是针对 c1 中的 9 个、c3 中的 10 个和 c4 中的 10 个，并且在商店中更新了可用性。对于第二次递归调用，我们拆解了一个 p2，并填写了一个 c1 和一个 c4 的订单，并将一个额外的 c2 放入商店；所以这个递归调用是针对 c1 中的 9 个、c3 中的 10 个和 c4 中的 9 个，并在商店中更新了可用性。

由于每次调用都会减少问题，因此递归调用系列将终止。递归调用应该返回一个成本指标，它要么表明调用未能找到解决方案，要么表明找到的解决方案成本是多少；该函数通过选择成本最低的解决方案来选择最佳解决方案。

我不确定，但您可以通过记住通话来加快速度。 Python 在 3.x 系列中有一个非常漂亮的内置新功能，functools.lru_cache() ;由于您将问题标记为“Python 3.2”，因此您可以使用它。

What is memoization and how can I use it in Python?

memoization 的工作原理是识别出该函数已经使用相同的参数被调用，并且只返回与以前相同的解决方案。所以它是一个缓存映射参数到答案。如果参数包含非必要数据(例如存储中有多少组件 c2)，则内存不太可能起作用。但是如果我们假设我们有产品 p1 和 p9，并且 p9 包含组件 c1 和 c9，那么为了我们的目的，拆卸 p1 之一或 p9 之一应该是等效的:它们具有相同的拆卸成本，并且它们都生产我们需要的组件(c1) 和一个我们不需要的 (c2 或 c9)。因此，如果我们正确使用递归调用参数，那么当我们开始尝试 p9 时，备忘录可以立即返回答案，并且可以节省大量时间。

嗯，现在想想，我们可能不能用functools.lru_cache()但我们可以自己记住。我们可以制作解决方案的缓存:将元组映射到值的字典，并构建仅包含我们想要缓存的参数的元组。那么在我们的函数中，我们做的第一件事就是检查解的缓存，如果这个调用相当于一个缓存的解，就返回它。

编辑:这是我到目前为止编写的代码。我还没有完成调试，所以它可能还没有产生正确的答案(我不确定，因为它需要很长时间而且我还没有让它完成运行)。这个版本正在传递字典，这对我关于内存的想法不太适用，但我想让一个简单的版本工作，然后担心加快速度。

此外，此代码将产品拆开并将它们作为组件添加到商店中，因此最终解决方案将首先说“拆开 10 个产品 A”之类的内容，然后它会说“拆开 20 个组件 alpha”或其他任何内容。换句话说，组件数量可以被认为是高的，因为它不区分已经在商店中的组件和通过拆卸产品放在那里的组件。

我现在没时间，暂时不会处理它，抱歉。

#!/usr/bin/python3

class Component:
    def __init__ (self, name): self.__name = name

    #def __repr__ (self): return 'Component {}'.format (self.__name)
    def __repr__ (self): return 'C_{}'.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)
    def __repr__ (self): return 'P_{}'.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 get_assembly_path (self, product, count):
        store = self.__items.copy()
        if product in store:
            take = min (count, store [product] )
            s_trivial = ('Take {} of {}'.format (take, product) )
            count -= take
            if not count:
                print(s_trivial)
                return
            dict_decr(store, product, take)
            product not in store

        order = {item:count for item in product.components}
        cost, solution = solver(order, store)
        if cost is None:
            print("No solution.")
            return

        print("Solution:")
        print(s_trivial)
        for item, count in solution.items():
            if isinstance(item, Component):
                print ('Take {} of {}'.format (count, item) )
            else:
                assert isinstance(item, Product)
                print ('Disassemble {} of {}'.format (count, item) )

    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) )

def str_d(d):
    lst = list(d.items())
    lst.sort(key=str)
    return "{" + ", ".join("{}:{}".format(k, v) for (k, v) in lst) + "}"

def dict_incr(d, key, n):
    if key not in d:
        d[key] = n
    else:
        d[key] += n

def dict_decr(d, key, n):
    assert d[key] >= n
    d[key] -= n
    if d[key] == 0:
        del(d[key])

def solver(order, store):
    """
    order is a dict mapping component:count
    store is a dict mapping item:count

    returns a tuple: (cost, solution)
        cost is a cost metric estimating the expense of the solution
        solution is a dict that maps item:count (how to fill the order)

    """
    print("DEBUG: solver: {} {}".format(str_d(order), str_d(store)))
    if not order:
        solution = {}
        cost = 0
        return (cost, solution)

    solutions = []
    for item in store:
        if not isinstance(item, Component):
            continue
        print("...considering: {}".format(item))
        if not item in order:
            continue
        else:
            o = order.copy()
            s = store.copy()
            dict_decr(o, item, 1)
            dict_decr(s, item, 1)
            if not o:
                # we have found a solution!  Return it
                solution = {}
                solution[item] = 1
                cost = 1
                print("BASIS: solver: {} {} / {} {}".format(str_d(order), str_d(store), cost, str_d(solution)))
                return (cost, solution)
            else:
                cost, solution = solver(o, s)
                if cost is None:
                    continue  # this was a dead end
                dict_incr(solution, item, 1)
                cost += 1
                solutions.append((cost, solution))

    for item in store:
        if not isinstance(item, Product):
            continue
        print("...Product components: {} {}".format(item, item.components))
        assert isinstance(item, Product)
        if any(c in order for c in item.components):
            print("...disassembling: {}".format(item))
            o = order.copy()
            s = store.copy()
            dict_decr(s, item, 1)
            for c in item.components:
                dict_incr(s, c, 1)
            cost, solution = solver(o, s)
            if cost is None:
                continue  # this was a dead end
            cost += 1 # cost of disassembly
            solutions.append((cost, solution))
        else:
            print("DEBUG: ignoring {}".format(item))

    if not solutions:
        print("DEBUG: *dead end*")
        return (None, None)
    print("DEBUG: finding min of: {}".format(solutions))
    return min(solutions)



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)
store.get_assembly_path(p3, 20)

关于python - 优化产品组装/拆卸，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15071659/