优化产品装配/拆卸

Question

我有一个包含物品的商店.每个项目都是一个组件(它是一个组件)或一个由各种组件组成的产品(但从不包含2个或更多相同的组件).

现在,当我想要从商店购买产品时,有各种各样的场景:

• 商店包含必要数量的产品.
• 商店包含我可以组装产品的组件.
• 商店包含与所需产品共享组件的产品.我可以拆卸它们并组装所需的物品.
• 以上任意组合.

下面你可以看到我的代码到目前为止(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 action"是组装或拆卸一种产品的行为,无论涉及多少组件.我正在寻找最少数量的触摸物品,无论它们是否与众不同.

也就是说,拆解产品A的20个比拆解产品A的10个和产品B的另外5个更好？

后者更接近最佳状态.

此外,您说您希望避免遗留许多组件,但在当前代码中,所有未被请求的产品使用的反汇编组件都将丢失.这是故意的(也就是说,你想丢掉其他组件),还是一个bug？

该方法getAssemblyPath仅确定如何获取项目的路径.它没有碰到实际的商店.它决不会分配给self.__items.将其视为向商店发出订单的功能,保留他在(中间)未来必须做的事情,以便从他的商店中获得所需数量的所需商品.

-

编辑2:

解决这个问题的第一个显而易见的(或至少对我很明显的)方法是首先搜索那些与所需产品共享最大组件数量的产品,因为每个反汇编都会获得更多所需的组件.但遗憾的是,这并不一定能产生最佳路径.举个例子:

产物A由组分α,β,γ,δ,ε和ζ组成.

产品B由组分α,β,η,δ,ε和θ组成.

产物C由组分α,β,γ,ι,κ和λ组成.

产品D由组分μ,ν,ξ,δ,ε和ζ组成.

我们在A的商店0,B的100,C的100和D的100.我们要求A的10个.现在如果我们首先看到与A共享大部分组件的产品,我们将找到B.我们拆卸10个B得到α,β,δ和ε各10.但是我们需要拆解10个C(得到γ)和10个D(得到ζ).这将是40个动作(30个拆卸和10个组装).但最好的方法是拆卸10个C和10个D(30个动作,20个拆卸和10个组装).

-

编辑3:

你不需要发布python代码来赢得赏金.只是向我解释算法,并证明它确实产生了最佳路径,或者如果存在多个路径则是最佳路径之一.

Answer 1

我认为这里的关键是确定每个购买案例的潜在成本，以便正确组合购买案例以最佳方式最小化成本函数。（那么它就简单地简化为背包问题）

下面的内容可能不是最佳的，但这里是我的意思的一个例子：

1.任何最终产品的“成本”都是实际成本（以货币形式）。

2.任何可以组装成最终产品（给定其他单独的产品/组件）但不需要拆卸的组件或产品都按其实际价格（以货币计）加上少量税（待定）。

3.任何可以促进最终产品组装但需要拆卸的组件或产品，其价格均以货币计算，加上组装成最终产品的小额税和每次所需拆卸的小额税。（也许与装配税的价值相同？）。

注意：这些“税费”将适用于占用同一箱子的所有子产品。

...其他可能的情况依此类推

然后，找到店面中可用的能够组装成最终产品的所有可能的组件和产品组合。将这些“组装列表”放入由您选择的成本函数确定的成本排序列表中。之后，开始创建尽可能多的第一个（最低成本）“装配列表”（通过检查装配列表中的所有项目是否仍然在商店中可用 - 即您已经将它们用于之前的装配）。一旦您无法再创建此案例，请将其从列表中弹出。重复此操作，直到“构建”出您需要的所有最终产品。

注意：每次“组装”最终产品时，您都需要减少当前“组装列表”中每个产品的全局计数器。

希望这能让讨论朝着正确的方向发展。祝你好运！