从较小的包裹中填写订单？

Question

输入是一个整数，指定要订购的数量。必须使用预定义的包装尺寸来创建该订单。例如Packs3 for $55 for $99 for $16对于输入顺序 13，输出应为：2x5 + 1x3到目前为止，我有以下方法：remaining_order = 13package_numbers = [9,5,3]required_packages = []while remaining_order > 0:    found = False    for pack_num in package_numbers:        if pack_num <= remaining_order:            required_packages.append(pack_num)            remaining_order -= pack_num            found = True            break    if not found:        break但这会导致错误的结果：1x9 + 1x3 剩余：1

Answer 1

那么，您需要用包裹填充订单以使总价最高吗？这被称为背包问题。在维基百科的那篇文章中，您会发现几个用 Python 编写的解决方案。

更准确地说，您需要一个解决无界背包问题的方法，这与流行的 0/1 背包问题（每件物品只能打包一次）形成对比。这是Rosetta 的工作代码：

from itertools import product

NAME, SIZE, VALUE = range(3)

items = (

    # NAME, SIZE, VALUE

    ('A', 3, 5),

    ('B', 5, 9),

    ('C', 9, 16))

capacity = 13

def 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, bagged

if __name__ == '__main__':

    value, size, numbagged, bagged = knapsack_unbounded_enumeration(items, capacity)

    print(value)

    print(bagged)

输出是：

23

['1x3', '2x5']

请记住，这是一个 NP-hard 问题，因此当您输入一些大值时它会崩溃:)

Answer 2

您可以使用itertools.product：

import itertools

remaining_order = 13

package_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 itertools

from collections import Counter

remaining_order = 13

package_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 + 1x3

0

Answer 3

由于没有找到关于对象函数的声明，我假设您的目标是在包的能力范围内最大化包的价值。

说明：时间复杂度是固定的。最佳解决方案可能不是尽可能多地填充最高值的项目，您必须搜索所有可能的组合。但是，您可以重复使用您搜索过的可能的最佳解决方案以节省空间。例如，[5,5,3]源自添加3到先前的[5,5]尝试，因此可以“缓存”中间结果。您可以使用数组或使用集合来存储可能的解决方案。下面的代码运行与 rosetta 代码相同的性能，但我认为它更清晰。

要进一步优化，请使用为 设置的优先级opts。

costs = [3,5,9]

value = [5,9,16]

volume = 130

# solutions

opts = set()

opts.add(tuple([0]))

# calc total value

cost_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 solutions

def 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 cur

while sum(optimize_max_return(opts)) <= volume - min(costs):

    opts = opts.union(possible_solutions())

print(optimize_max_return(opts))

如果您的要求是“只装满包装”，那么使用每个项目的体积会更简单。