This is how I would solve this problem. I wanted to write code for this, but I don’t think I have the time.
Recursively, you can find the best solution. Create a data structure that represents the state of the part store and the current query. Now, for each piece you need, make a series of recursive calls that try different ways to fill out the order. The key is that when you try to fill out an order, you get some of the work done, so the recursive call is now a slightly simpler version of the same problem.
Here is an example based on your example. We need to fill out orders for product 3 (p3), which consists of components c1, c3 and c4. Our order is for 20 p3, and we have 10 p3 in stock, so we trivially fill the order for the first 10 p3. Now our order is 10 of p3, but we can consider it as the order of 10 of c1, 10 of c3 and 10 c4. For the first recursive call, we parse p1 and fill in the order for one c1 and add additional c2 to the storage; therefore this recursive call is for 9 of c1, 10 of c3 and 10 c4, with updated store availability. For the second recursive call, we will parse p2 and fill out the order for c1 and c4 and add additional c2 to the repository; therefore, this recursive call is for 9 of c1, 10 of c3, and 9 c4 with updated storage availability.
As each call reduces the problem, the recursive series of calls is terminated. Recursive calls should return a cost metric that either signals that the call could not find a solution, or signals how much the solution found is worth; the function selects the best solution, choosing the solution with the lowest cost.
I'm not sure, but you could speed it up by notifying you of calls. Python has a really great built-in version in the 3.x series, functools.lru_cache() ; since you marked your question as "Python 3.2", this is available to you.
What is memoization and how can I use it in Python?
Recollection works by recognizing that the function is already being called with the same arguments and simply returning the same solution as before. Thus, these are arguments for matching the cache. If the arguments include non-essential data (for example, how many c2 components are in storage), then unmounting is less likely to work. But if we assume that we have products p1 and p9, and p9 contains components c1 and c9, then for our purposes, disassembling one of p1 or one of p9 should be equivalent: they have the same disassembly cost, and both of them produce what we need component (c1) and one that we do not need (c2 or c9). Therefore, if we correctly receive the arguments of the recursive call, memoization may simply return an instant response when we move on to p9, and this can save a lot of time.
Hmm, now that I think about it, we probably can't use functools.lru_cache() , but we can just memoize ourselves. We can create a solution cache: matching a dictionary with values ​​and building tuples in which there are only those arguments that we want to cache. Then in our function, the first thing we do is check the cache solutions, and if this call is equivalent to a cached solution, just return it.
EDIT: Here is the code that I have written so far. I didn’t finish debugging it so that it probably wouldn’t give the right answer yet (I’m not sure because it takes a lot of time and I didn’t let it finish the job). This version goes through dictionaries that will not work well with my memoizing ideas, but I would like to get a simple version and then worry about speeding it up.
In addition, this code combines the products and adds them to the repository as components, so the final solution will first say something like “Separate 10 products A” and then say “Take 20 component alpha” or something else. In other words, the component count can be considered high, because it does not distinguish between the components that were already in the store and the components that were placed there by disassembling the products.
Now I do not have time and I will not work on it for a while, sorry.
#!/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)