3

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

现在，用户不必确定要抓取多少 45 磅、35 磅、25 磅等重量，并且应用程序可以显示一个表格，其中包含所需的每种尺寸的重量数量，这将是一件好事。

我的问题是，鉴于我们有无限数量的 5 磅、10 磅、25 磅、35 磅和 45 磅的权重，那么能够对阵列中的每个权重求和的最佳数量是多少？最佳是首先总重量最少，然后总重量最轻。

例如，假设我想优化 {25, 35, 45}，那么如果我的答案数组是 {num_5lbs, num_10lbs, num_25lbs, num_35lbs, num_45lbs} 我们可以做 {0,0,1,1,1} 但然后总计为 25+35+45=105 磅。我们也可以做 {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磅。

4

2 回答 2

1

您可以将其解决为整数线性规划问题。

引入整数变量n5, n10, n25, n35, n45来计算可能解决方案中每个权重的数量。

优化目标为：

minimize (n5+n10+n25+n35+n45) * 1000 + 5*n5 + 10*n10 + 25*n25 + 35*n35 + n45

这里，1000是大于会话中出现的最大总权重的任何整数，并且此函数旨在首先最大化权重总数，然后是总权重。

接下来，假设是您想要的目标权重w[1]。w[k]添加（非负）整数变量a5[i]、a10[i]、a25[i]、a35[i]和a45[i]（i范围超过1到k），并添加这些线性约束：

a5[i]*5 + a10[i]*10 + a25[i]*25 + a35[i]*35 + a45[i]*45 = w[i]
a5[i] <= n5
a10[i] <= n10
a25[i] <= n25
a35[i] <= n35
a45[i] <= n45

这些约束保证w[i]可以从解决方案中有限数量的权重构建。

我不知道在您的应用程序中包含 ILP 求解器而不是暴力破解解决方案甚至只是使用启发式算法来产生局部最优但不一定是全局最优的解决方案是否有意义。

于 2016-04-29T00:31:34.803 回答
1

你抓住了我这个有竞争力的程序员。

使用动态编程（记忆），我能够将运行时间降低到合理的水平。

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

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

接下来我们有主要的 DP 功能。walk接受一个已使用权重的有序列表（最初为空）并pos告诉我们我们已经考虑了哪些权重（最初为零）。walk这减少了对from O(n!)to的调用次数O(2^n)。walk也被记忆，进一步降低执行时间从O(2^n)到O(n)。

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

  • pos >= len(weights)如果 pos 大于权重的长度，我们已经检查了所有的权重，并且我们完成了递归。
  • len(used) > max(targets) / min(weights)这是对要使用的权重数量的弱限制。如果有办法只使用最小的权重并且仍然通过最大的目标，我们知道我们已经检查了足够多的数字，并且这个分支是无用的。继续。
  • len(used) > bwnumbwnum到目前为止，最佳答案中使用的权重数量在哪里。由于这是我们的主要标准，当我们选择的权重超过时，我们可以停止递归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

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

于 2016-04-29T00:17:07.720 回答