米琪卡哇伊
那么，您需要用包裹填充订单以使总价最高吗？这被称为背包问题。在维基百科的那篇文章中，您会发现几个用 Python 编写的解决方案。更准确地说，您需要一个解决无界背包问题的方法，这与流行的 0/1 背包问题（每件物品只能打包一次）形成对比。这是Rosetta 的工作代码：from itertools import productNAME, SIZE, VALUE = range(3)items = ( # NAME, SIZE, VALUE ('A', 3, 5), ('B', 5, 9), ('C', 9, 16))capacity = 13def knapsack_unbounded_enumeration(items, C): # find max of any one item max1 = [int(C / item[SIZE]) for item in items] itemsizes = [item[SIZE] for item in items] itemvalues = [item[VALUE] for item in items] # def totvalue(itemscount, =itemsizes, itemvalues=itemvalues, C=C): def totvalue(itemscount): # nonlocal itemsizes, itemvalues, C totsize = sum(n * size for n, size in zip(itemscount, itemsizes)) totval = sum(n * val for n, val in zip(itemscount, itemvalues)) return (totval, -totsize) if totsize <= C else (-1, 0) # Try all combinations of bounty items from 0 up to max1 bagged = max(product(*[range(n + 1) for n in max1]), key=totvalue) numbagged = sum(bagged) value, size = totvalue(bagged) size = -size # convert to (iten, count) pairs) in name order bagged = ['%dx%d' % (n, items[i][SIZE]) for i, n in enumerate(bagged) if n] return value, size, numbagged, baggedif __name__ == '__main__': value, size, numbagged, bagged = knapsack_unbounded_enumeration(items, capacity) print(value) print(bagged)输出是：23['1x3', '2x5']请记住，这是一个 NP-hard 问题，因此当您输入一些大值时它会崩溃:)
冉冉说
您可以使用itertools.product：import itertoolsremaining_order = 13package_numbers = [9,5,3]required_packages = []a=min([x for i in range(1,remaining_order+1//min(package_numbers)) for x in itertools.product(package_numbers,repeat=i)],key=lambda x: abs(sum(x)-remaining_order))remaining_order-=sum(a)print(a)print(remaining_order)输出：(5, 5, 3)0这只是执行以下步骤：13在包含所有产品值的列表中获取最接近的值。然后简单地让它修改remaining_order.如果你想输出'x'：import itertoolsfrom collections import Counterremaining_order = 13package_numbers = [9,5,3]required_packages = []a=min([x for i in range(1,remaining_order+1//min(package_numbers)) for x in itertools.product(package_numbers,repeat=i)],key=lambda x: abs(sum(x)-remaining_order))remaining_order-=sum(a)print(' '.join(['{0}x{1}'.format(v,k) for k,v in Counter(a).items()]))print(remaining_order)输出：2x5 + 1x30
狐的传说
由于没有找到关于对象函数的声明，我假设您的目标是在包的能力范围内最大化包的价值。说明：时间复杂度是固定的。最佳解决方案可能不是尽可能多地填充最高值的项目，您必须搜索所有可能的组合。但是，您可以重复使用您搜索过的可能的最佳解决方案以节省空间。例如，[5,5,3]源自添加3到先前的[5,5]尝试，因此可以“缓存”中间结果。您可以使用数组或使用集合来存储可能的解决方案。下面的代码运行与 rosetta 代码相同的性能，但我认为它更清晰。要进一步优化，请使用为 设置的优先级opts。costs = [3,5,9]value = [5,9,16]volume = 130# solutionsopts = set()opts.add(tuple([0]))# calc total valuecost_val = dict(zip(costs, value))def total_value(opt): return sum([cost_val.get(cost,0) for cost in opt])def possible_solutions(): solutions = set() for opt in opts: for cost in costs: if cost + sum(opt) > volume: continue cnt = (volume - sum(opt)) // cost for _ in range(1, cnt + 1): sol = tuple(list(opt) + [cost] * _) solutions.add(sol) return solutionsdef optimize_max_return(opts): if not opts: return tuple([]) cur = list(opts)[0] for sol in opts: if total_value(sol) > total_value(cur): cur = sol return curwhile sum(optimize_max_return(opts)) <= volume - min(costs): opts = opts.union(possible_solutions())print(optimize_max_return(opts))如果您的要求是“只装满包装”，那么使用每个项目的体积会更简单。