210406アルゴリズム

アルゴリズム210406
<差が最大>
n個数えた場合(3<=N<=8)
|A[0] - A[1]| + |A[1] - A[2]| + … + |A[N-2] - A[N-1]|
最大の問題
N! = 8! = 40320

Pythonソース

def next_permutation(a):
i = len(a)-1
while i > 0 and a[i-1] >= a[i]:
i -= 1
if i <= 0:
return False
j = len(a)-1
while a[j] <= a[i-1]:
j -= 1

a[i-1],a[j] = a[j],a[i-1]

j = len(a)-1
while i < j:
    a[i],a[j] = a[j],a[i]
    i += 1
    j -= 1

return True

def calc(a):
ans = 0
for i in range(1, len(a)):
ans += abs(a[i]-a[i-1])
return ans
n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 0
while True:
temp = calc(a)
ans = max(ans, temp)
if not next_permutation(a):
break
print(ans)
『外判員巡り』
英語に翻訳されたSalesman Problem(TSP)
1番からN番までの都市があります.
一つの都市から、Nのすべての都市を経て、元の都市に戻ります.
お帰りなさい.(かつて行った町には戻れない)
この時点で必要なコストが最も低い

Pythonソース

def next_permutation(a):
i = len(a)-1
while i > 0 and a[i-1] >= a[i]:
i -= 1
if i <= 0:
return False
j = len(a)-1
while a[j] <= a[i-1]:
j -= 1

a[i-1],a[j] = a[j],a[i-1]

j = len(a)-1
while i < j:
    a[i],a[j] = a[j],a[i]
    i += 1
    j -= 1

return True

n = int(input())
w = [list(map(int,input().split())) for _ in range(n)]
d = list(range(n))
ans = 2147483647
while True:
ok = True
s = 0
for i in range(0, n-1):
if w[d[i]][d[i+1]] == 0:
ok = False
break
else:
s += w[d[i]][d[i+1]]
if ok and w[d[-1]][d[0]] != 0:
s += w[d[-1]][d[0]]
ans = min(ans, s)
if not next_permutation(d):
break
print(ans)
<宝くじ>
同じ数があってもシーケンスを生成できます.
与えられたK個の入力数の中から6個の数を選択する問題.
再帰関数で解くことができます.
再帰関数は、1つの関数から自分を再呼び出してタスクを実行することによって、所与の問題を解決する方法である.
Pythonを使用すると、Pythonは関数の深さ制限がほぼ1000であることに気づくので、995回程度戻るとシャットダウンします.
def next_permutation(a):
i = len(a)-1
while i > 0 and a[i-1] >= a[i]:
i -= 1
if i <= 0:
return False
j = len(a)-1
while a[j] <= a[i-1]:
j -= 1

a[i-1],a[j] = a[j],a[i-1]

j = len(a)-1
while i < j:
    a[i],a[j] = a[j],a[i]
    i += 1
    j -= 1

return True

while True:
n, a = list(map(int,input().split()))
if n == 0:
break
d = [0](n-6)+[1]*6
ans = []
while True:
cur = [a[i] for i in range(n) if d[i] == 1]
ans.append(cur)
if not next_permutation(d):
break
ans.sort()
for v in ans:
print(' '.join(map(str,v)))
print()