python - 用 Python 解决难题

Question

我有一个难题，我想用 Python 解决它。

谜：

一位商人有一个 40 公斤的重量，他在他的商店中使用。有一次，它从他手中掉了下来，碎成了四块。但令人惊讶的是，现在他可以通过这 4 件的组合来称重 1 公斤到 40 公斤之间的任何重量。

所以问题是，这 4 件的重量是多少？

现在我想用 Python 解决这个问题。

我从这个谜题中得到的唯一限制是 4 块的总和是 40。这样我就可以过滤总和为 40 的所有 4 个值的集合。

import itertools as it

weight = 40
full = range(1,41)
comb = [x for x in it.combinations(full,4) if sum(x)==40]

length of comb = 297

现在我需要检查每组值comb并尝试所有操作组合。

例如，如果(a,b,c,d)是中的第一组值comb，我需要检查a,b,c,d,a+b,a-b, .................a+b+c-d,a-b+c+d........等等。

我尝试了很多，但我被困在这个阶段，即如何检查所有这些计算组合到每组 4 个值。

问题：

1）我认为我需要列出所有可能的组合[a,b,c,d] and [+,-]。

2）有没有人有更好的主意并告诉我如何从这里继续前进？

另外，我想在没有任何外部库的帮助下完全做到这一点，只需要使用 python 的标准库。

编辑：对不起，迟到的信息。它的答案是 (1,3,9,27)，这是我几年前发现的。我已经检查并验证了答案。

编辑：目前，fraxel的答案与time = 0.16 ms. 更好更快的方法总是受欢迎的。

问候

方舟

score 25 · Accepted Answer

较早的演练答案：

我们知道0 到 40 之间a*A + b*B + c*C + d*D = x的所有人，并且仅限于. 显然。下一种情况是，所以显然最小的移动是删除一个元素（这是唯一可能导致成功平衡 39 的移动）：xa, b, c, d-1, 0, 1A + B + C + D = 40x = 39

A + B + C = 39，所以D = 1，根据需要。

下一个：

A + B + C - D = 38

下一个：

A + B + D = 37，所以C = 3

然后：

A + B = 36

然后：

A + B - D = 35

A + B - C + D = 34

A + B - C = 33

A + B - C - D = 32

A + C + D = 31，所以A = 9

所以B = 27

所以权重是1, 3, 9, 27

实际上，这可以从它们都必须是 3 的倍数这一事实中立即推断出来。

有趣的更新：

因此，这里有一些 python 代码，可以为任何跨越空间的下降权重找到最小权重集：

def find_weights(W):
    weights = []
    i = 0
    while sum(weights) < W:
        weights.append(3 ** i)
        i += 1
    weights.pop()
    weights.append(W - sum(weights))
    return weights

print find_weights(40)
#output:
[1, 3, 9, 27]

为了进一步说明这一解释，可以将问题视为跨越数字空间的最小权重数[0, 40]。很明显，每个重量可以做的事情是三元/三元（增加重量，去除重量，把重量放在另一边）。因此，如果我们(A, B, C, D)按降序编写（未知）权重，我们的动作可以总结为：

    ABCD:   Ternary:
40: ++++     0000
39: +++0     0001
38: +++-     0002
37: ++0+     0010
36: ++00     0011
35: ++0-     0012
34: ++-+     0020
33: ++-0     0021
32: ++--     0022
31: +0++     0100
etc.

我把从 0 到 9 的三进制数放在旁边，以说明我们实际上是在一个三进制数系统中（以 3 为底）。我们的解决方案总是可以写成：

3**0 + 3**1 +3**2 +...+ 3**N >= Weight

对于这成立的最小 N。最小解决方案将始终采用这种形式。

此外，我们可以轻松解决大权重问题并找到跨越空间的最小块数：

一个人掉下一个已知重量 W，它会碎成碎片。他的新砝码允许他称重最大为 W 的任何重量。有多少个砝码，它们是什么？

#what if the dropped weight was a million Kg:
print find_weights(1000000)
#output:
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 202839]

尝试对大重量和未知数量的件使用排列！

score 8 · Accepted Answer

这是一个蛮力的 itertools 解决方案：

import itertools as it

def merchant_puzzle(weight, pieces):
    full = range(1, weight+1)
    all_nums = set(full)
    comb = [x for x in it.combinations(full, pieces) if sum(x)==weight]
    funcs = (lambda x: 0, lambda x: x, lambda x: -x)
    for c in comb:
        sums = set()
        for fmap in it.product(funcs, repeat=pieces):
            s = sum(f(x) for x, f in zip(c, fmap))
            if s > 0:
                sums.add(s)
                if sums == all_nums:
                    return c

>>> merchant_puzzle(40, 4)
(1, 3, 9, 27)

有关其工作原理的解释，请查看Avaris 给出的答案，这是相同算法的实现。

score 4 · Accepted Answer

你很接近，非常接近:)。

由于这是您要解决的难题，因此我将提供指点。对于这部分：

例如，如果 (a,b,c,d) 是 comb 中的第一组值，我需要检查 a,b,c,d,a+b,ab,...... .....a+b+cd,a-b+c+d........等等。

考虑一下这一点：每个重量都可以放在一个秤上，另一个或两者都没有。所以对于的情况a，这可以表示为[a, -a, 0]。其他三个也一样。现在您需要所有可能的配对以及每种重量的这 3 种可能性（提示：）itertools.product。然后，对配对的可能测量（比如说：(a, -b, c, 0)）仅仅是这些（a-b+c+0）的总和。

剩下的就是检查您是否可以“测量”所有需要的重量。set在这里可能会派上用场。

PS：正如评论中所述，对于一般情况，这些划分的权重可能没有必要区分（对于这个问题）。你可能会重新考虑itertools.combinations。

score 2 · Accepted Answer

我蛮力逼出第二部分的地狱。

如果您不想看到答案，请不要单击此按钮。显然，如果我在排列方面做得更好，这将需要更少的剪切/粘贴搜索/替换：

http://pastebin.com/4y2bHCVr

score 0 · Accepted Answer

我不知道 Python 语法，但也许你可以解码这个 Scala 代码；从第二个 for 循环开始：

def setTo40 (a: Int, b: Int, c: Int, d: Int) = {

val vec = for (
  fa <- List (0, 1, -1);
  fb <- List (0, 1, -1);
  fc <- List (0, 1, -1);
  fd <- List (0, 1, -1);
  prod = fa * a + fb * b + fc * c + fd * d;
  if (prod > 0)
  ) yield (prod)

  vec.toSet
}

for (a <- (1 to 9);
  b <- (a to 14);
  c <- (b to 20);
  d = 40-(a+b+c)
  if (d > 0)) { 
    if (setTo40 (a, b, c, d).size > 39)
      println (a + " " + b + " " + c + " " + d)
  }

score 0 · Accepted Answer

使用砝码 [2, 5, 15, 18]，您还可以测量 1 到 40 公斤之间的所有物体，尽管其中一些需要间接测量。例如，要测量一个重 39 公斤的物体，您首先将其与 40 公斤进行比较，然后天平将悬垂到 40 公斤的一侧（因为 39 < 40），但是如果您移除 2 公斤的重量，它会悬垂到另一侧（因为39 > 38），因此您可以得出物体重量为 39 公斤的结论。

更有趣的是，使用权重 [2, 5, 15, 45]，您可以测量所有重量不超过 67 公斤的物体。

score 0 · Accepted Answer

如果有人不想导入库来导入组合/烫发，这将生成所有可能的 4 步策略......

# generates permutations of repeated values
def permutationsWithRepeats(n, v):
    perms = []
    value = [0] * n
    N = n - 1
    i = n - 1

    while i > -1:
        perms.append(list(value))

        if value[N] < v:
            value[N] += 1
        else:
            while (i > -1) and (value[i] == v):
                value[i] = 0
                i -= 1

            if i > -1:
                value[i] += 1
                i = N

    return perms

# generates the all possible permutations of 4 ternary moves
def strategy():
    move = ['-', '0', '+']
    perms = permutationsWithRepeats(4, 2)

    for i in range(len(perms)):
        s = ''

        for j in range(4):
            s += move[perms[i][j]]

        print s

# execute
strategy()

score 0 · Accepted Answer

我的解决方案如下：

    #!/usr/bin/env python3

weight = 40
parts = 4
part=[0] * parts

def test_solution(p, weight,show_result=False):
    cv=[0,0,0,0]
    for check_weight in range(1,weight+1):
        sum_ok = False
        for parts_used in range(2 ** parts):
            for options in range(2 ** parts):
                for pos in range(parts):
                    pos_neg = int('{0:0{1}b}'.format(options,parts)[pos]) * 2 - 1
                    use = int('{0:0{1}b}'.format(parts_used,parts)[pos])
                    cv[pos] = p[pos] * pos_neg * use
                if sum(cv) == check_weight:
                    if show_result:
                        print("{} = sum of:{}".format(check_weight, cv))
                    sum_ok = True
                    break
        if sum_ok:
            continue
        else:
            return False
    return True

for part[0] in range(1,weight-parts):
    for part[1] in range(part[0]+1, weight - part[0]):
        for part[2] in range( part[1] + 1 , weight - sum(part[0:2])):
            part[3] = weight - sum(part[0:3])
            if test_solution(part,weight):
                print(part)
                test_solution(part,weight,True)
                exit()

它为您提供给定权重的所有解决方案

score 0 · Accepted Answer

比我之前的答案更有活力，因此它也适用于其他数字。但是分成 5 个和平需要一些时间：

#!/usr/bin/env python3

weight = 121
nr_of_parts = 5

# weight = 40
# nr_of_parts = 4

weight = 13
nr_of_parts = 3


part=[0] * nr_of_parts

def test_solution(p, weight,show_result=False):
    cv=[0] * nr_of_parts
    for check_weight in range(1,weight+1):
        sum_ok = False
        for nr_of_parts_used in range(2 ** nr_of_parts):
            for options in range(2 ** nr_of_parts):
                for pos in range(nr_of_parts):
                    pos_neg = int('{0:0{1}b}'.format(options,nr_of_parts)[pos]) * 2 - 1
                    use = int('{0:0{1}b}'.format(nr_of_parts_used,nr_of_parts)[pos])
                    cv[pos] = p[pos] * pos_neg * use
                if sum(cv) == check_weight:
                    if show_result:
                        print("{} = sum of:{}".format(check_weight, cv))
                    sum_ok = True
                    break
        if sum_ok:
            continue
        else:
            return False
    return True

def set_parts(part,position, nr_of_parts, weight):
    if position == 0:
        part[position] = 1
        part, valid = set_parts(part,position+1,nr_of_parts,weight)
        return part, valid
    if position == nr_of_parts - 1:
        part[position] = weight - sum(part)
        if part[position -1] >= part[position]:
            return part, False
        return part, True
    part[position]=max(part[position-1]+1,part[position])
    part, valid = set_parts(part, position + 1, nr_of_parts, weight)
    if not valid:
        part[position]=max(part[position-1]+1,part[position]+1)
        part=part[0:position+1] + [0] * (nr_of_parts - position - 1)
        part, valid = set_parts(part, position + 1, nr_of_parts, weight)
    return part, valid

while True:
    part, valid = set_parts(part, 0, nr_of_parts, weight)
    if not valid:
        print(part)
        print ('No solution posible')
        exit()
    if test_solution(part,weight):
        print(part,'    ')
        test_solution(part,weight,True)
        exit()
    else:
        print(part,'   ', end='\r')

python - 用 Python 解决难题

9 回答 9

Related

Reference