19

パズルが 1 つあり、Python を使用して解決したいと考えています。

パズル：

ある商人は、自分の店で使用していた 40 kg の重りを持っています。一度、手から落ちて四つに割れた。しかし驚くべきことに、今ではこの 4 つのピースの組み合わせで 1 kg から 40 kg までの任意の重量を量ることができます。

そこで質問なのですが、この 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 の標準ライブラリのみを使用する必要があります。

EDIT：情報が遅くなって申し訳ありません。その答えは (1,3,9,27) で、数年前に見つけました。回答を確認して確認しました。

編集：現在、fraxelの答えはで完璧に機能しtime = 0.16 msます。より良い、より速いアプローチはいつでも大歓迎です。

よろしく

アーク

4

9 に答える 9

25

以前のウォークスルー回答:

私たちは 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 進数システム (基数 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]

重量が大きく、ピース数が不明な場合は、順列を使用してみてください!!

于 2012-04-30T19:08:24.673 に答える
8

ブルートフォース 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 の回答を参照してください。これは同じアルゴリズムの実装です。

于 2012-04-30T19:06:06.907 に答える
4

あなたは近いです、非常に近いです:)。

これはあなたが解決したいパズルなので、私はヒントだけを与えます. この部分について:

たとえば、(a,b,c,d) がcombの最初の値のセットである場合、a,b,c,d,a+b,ab, .............を確認する必要があります。 .....a+b+cd、a-b+c+d........など。

これを考慮してください: 各重量は、1 つのスケールに置くことができます。したがって、 の場合a、これは として表すことができます[a, -a, 0]。他の3つも同様です。ここで、重みごとにこれらの 3 つの可能性を持つすべての可能な組み合わせが必要です (ヒント: itertools.product)。次に、ペアリングの可能な測定値 (たとえば、(a, -b, c, 0)) は、これらの合計 ( a-b+c+0) にすぎません。

あとは、必要なすべての重みを「測定」できるかどうかを確認するだけです。setここで便利かもしれません。

PS: コメントで述べたように、一般的なケースでは、これらの分割された重みを区別する必要はないかもしれません (この問題ではそうです)。再考するかもしれませんitertools.combinations。

于 2012-04-30T19:06:17.263 に答える
2

私は第二部から力ずくで地獄を追い出しました。

答えを見たくない場合は、これをクリックしないでください。明らかに、私が順列に長けていれば、カット/ペーストの検索/置換がはるかに少なくて済みます:

http://pastebin.com/4y2bHCVr

于 2012-04-30T19:07:01.820 に答える
0

Python の構文はわかりませんが、この Scala コードを解読できるかもしれません。2 番目の 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)
  }
于 2012-04-30T21:28:45.477 に答える
0

コンボ/パーマをインポートするためにライブラリをインポートしたくない場合は、これにより、可能なすべての 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()
于 2017-08-13T18:23:37.167 に答える
0

重み [2、5、15、18] を使用すると、1 ～ 40 kg のすべてのオブジェクトを測定することもできますが、それらの一部は間接的に測定する必要があります。たとえば、39kg の物体を測定するには、最初にそれを 40kg と比較し、天びんは 40kg 側に保留されます (39 < 40 のため)。ただし、2kg の重量を削除すると、反対側に保留されます ( 39 > 38) したがって、オブジェクトの重量は 39kg と結論付けることができます。

さらに興味深いことに、重り [2、5、15、45] を使用すると、67kg までのすべてのオブジェクトを測定できます。

于 2013-03-22T11:33:19.700 に答える