Question

我有一个家庭工作,在这个工作中,我需要在下午解决这一问题:

There are N houses in a street. Every house s garden can have only 1 out of 3 colors of flower planted.
There is a list (in a file) which consists of price for every color of flower for every property and it looks something like that:

Every row represents one house and every column one color. (lets say White, Yellow, Red) What I have to do is to find a cheapest way to plant flowers in this neighborhood, but if a 1 house has certain color planted then the houses next to it cant plant that color. So for set of 4 houses:

housescolors   w y r
H1              5 6 7

H2              3 7 9

H3              6 7 3

H4              1 8 4

包括该规则在内的最廉价方式是:6+3+1 = 13. 因此,颜色是黄色、白、红、白。

因此,我已经找到了解决这一问题的办法,使用惯用器及其产品。我刚刚提出了一份清单,列出所有可能性,即第纳尔第一组[1,2,3],并排除了每组有2个相同相邻数字的人,然后,我就对每一种组合适用价格,并找到最廉价的价格。但是,随着这一解决办法的扩大,N(可能好像,20) 其速度非常缓慢,甚至可能因为记忆错误而坠毁。因此,我 m问是否有更快的解决办法。另外,如果任何人对问题有任何疑问,请他们问他们,那么我毛派的english夫可能对此问题作坏解释。

Edit - the code I have right now:

import itertools
file = open( domy.txt )
ceny = file.readlines()

for x in range(len(ceny)):
    ceny[x] = ceny[x][0:-1]

n = len(ceny)
domy = [[0]*3]*n

for x in range(n):
    test = ceny[x].split(   )

test = list(itertools.product([1, 2, 3], repeat=n))

i = 0
while i < len(test):
    t = 0
    while t < len(test[t])-1:
        if test[i][t] == test[i][t+1]:
            test.pop(i)
            i -= 1
            break
        t += 1
    i += 1

index = 0
i = 0
minimum = 0
while i < len(test):
    suma = 0
    if i == 0:
        j = 0
        for x in test[i]:
            if x == 1:
                suma += int(ceny[j][0])
            elif x == 2:
                suma += int(ceny[j][2])
            elif x == 3:
                suma += int(ceny[j][4])
            j += 1
        index = i
        minimum = suma
    else:
        j = 0
        for x in test[i]:
            if x == 1:
                suma += int(ceny[j][0])
            elif x == 2:
                suma += int(ceny[j][2])
            elif x == 3:
                suma += int(ceny[j][4])
            j += 1
        if suma < minimum:
            minimum = suma
            index = i
    i += 1

print(minimum)
print(test[index])

Answer 1

仅找到最低数额的基本算法通过各行各行,并跟踪与三个栏(例如:<代码>b)相距的最低数额,是迄今为止通过各行各行各行各处购买中流的最小数额。

def solve(rows):
    a = b = c = 0
    for x, y, z in rows:
        a, b, c = (
            min(b, c) + x,
            min(a, c) + y,
            min(a, b) + z
        )
    return min(a, b, c)

rows = [
    [5, 6, 7],
    [3, 7, 9],
    [6, 7, 3],
    [1, 8, 4]
]

print(solve(rows))

为了获得导致最低数额的选择清单,还要跟踪选择情况,并重建随后的道路。注:

Oh well... Here s one also computing the list. Instead of tracking just sums, track (sum,path) pairs:

def solve(rows):
    a = b = c = (0, None)
    def extend(a, b, z, i):
        sum, path = min(a, b)
        return sum + z, (i, path)
    for x, y, z in rows:
        a, b, c = (
            extend(b, c, x, 1),
            extend(a, c, y, 2),
            extend(a, b, z, 3)
        )
    sum, path = min(a, b, c)
    flat = []
    while path:
        i, path = path
        flat.append(i)
    return sum, flat[::-1]

rows = [
    [5, 6, 7],
    [3, 7, 9],
    [6, 7, 3],
    [1, 8, 4]
]

print(*solve(rows))

马达加斯加尝试:

友情链接