python - 从较小的包裹中完成订单？

Question

输入是一个整数，指定要订购的数量。 必须使用预定义的包装尺寸来创建该订单。

例如

Packs
3 for $5
5 for $9
9 for $16

对于输入订单 13，输出应为:

2x5 + 1x3

到目前为止，我有以下方法:

remaining_order = 13
package_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

那么，您需要用包裹填写订单以使总价最高吗？这被称为 Knapsack problem .在那篇维基百科文章中，您会找到几个用 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 问题，因此当您输入一些较大的值时它会失败 :)