algorithm - 扭转硬币变化(最小化权重数组)

Question

我正在构建一个应用程序，用于进行少于 10 种不同重量的锻炼。例如:锻炼可能需要 {30,40,45,50,55,65,70,80} 的重量。

现在，如果用户不必确定要抓取多少个 45 磅、35 磅、25 磅等，并且让应用程序显示一个包含每种尺寸的重量数量的表格，那就太好了需要。

我的问题是，鉴于我们有无限数量的 5lb、10lb、25lb、35lb 和 45lb 重量，能够将数组中的每个重量相加的最佳数量是多少？最优是总重量最少，其次是总重量最轻。

例如，假设我想优化 {25, 35, 45}，那么如果我的答案数组是 {num_5lbs, num_10lbs, num_25lbs, num_35lbs, num_45lbs} 我们可以做 {0,0,1,1,1}但总重量是 25+35+45=105lbs。我们也可以做 {0,2,1,0,0}，我认为这是最优的，因为它有 3 个重量，但总重量只有 45 磅。

另一个例子，假设我想优化 {30,40,50}，那么我们可以有 {1,2,1,0,0} 和 {1,1,1,1,0}。两者都使用4个砝码，但前者一共是5+20+25=50磅，而后者一共是5+10+25+35=75磅。

Answer 1

你在我身上发现了竞争激烈的程序员。

使用动态编程(记忆化)我能够将运行时间降低到一个合理的水平。

首先，我们定义了我们拥有的权重类型，以及我们想要达到的目标。

weights = [5, 10, 25, 35, 45]
targets = [30, 40, 45, 50, 55, 65, 70, 80]

接下来是主要的 DP 函数。 walk 采用一个有序的已用权重列表(最初为空)和一个 pos 告诉我们已经考虑了哪些权重(最初为零)。这将 walk 的调用次数从 O(n!) 降低到 O(2^n)。 walk 也被内存，进一步将执行时间从 O(2^n) 降低到 O(n)。

有一些基本情况，其中一些是为了性能而动态修改的:

• pos >= len(weights) 如果 pos 大于权重的长度，我们已经检查了所有的权重，并且我们完成了递归。
• len(used) > max(targets)/min(weights) 这是对要使用的权重数量的弱限制。如果有一种方法可以只使用最小的权重并仍然通过最大的目标，我们就知道我们已经检查了足够多的数字，并且这个分支是无用的。继续前进。
• len(used) > bwnum 其中 bwnum 是迄今为止最佳答案中使用的权重数。因为这是我们的主要标准，所以当我们选择的权重超过 bwnum 时，我们可以停止递归。这是一个很大的优化，假设我们很快找到任何有效答案。

对于a和b这两种情况，我们可以在pos处选择另一个权重，或者我们可以移动pos 转发。最好的(最短的，然后是最小的总和)被内存并返回。由于有两种情况，我们的分支因子为 2。

mem = {}
bwnum = len(weights)+1

def walk(used, pos):
    k = (used, pos)
    global bwnum, weights, targets

    if pos >= len(weights) or len(used) > bwnum or len(used) > max(targets) / min(weights):
        return used if valid(used) else (1e9,)*(bwnum+1)

    if k not in mem:
        a = walk(used + (weights[pos],), pos)
        b = walk(used, pos + 1)

        mem[k] = a if len(a) < len(b) or (len(a) == len(b) and sum(a) < sum(b)) else b
        if valid(mem[k]):
            bwnum = min(bwnum, len(mem[k]))

    return mem[k]

然后我们需要一个验证器函数来检查给定的权重列表是否足以达到所有目标。这可以进一步优化，但速度非常快。我将 80% 的执行时间花在了这个函数上。

from itertools import combinations

vmem = {}


def valid(used):
    if used not in vmem:
        tmap = {}
        for t in targets:
            tmap[t] = 0

        for le in range(1, len(used) + 1):
            for c in combinations(used, le):
                if sum(c) in tmap:
                    del tmap[sum(c)]

        vmem[used] = len(tmap) == 0

    return vmem[used]

最后，用空参数调用walk，并打印结果。

r = walk((), 0)
print r, len(r), sum(r)

哪些输出:

(5, 5, 10, 25, 35) 5 80

哦，顺便说一句，你的例子是正确的。谢谢。