[SWEA] 5209. [Python S/Wトラブルシューティング実施]5日間-最低生産コスト[D 3]
6186 ワード
📚 質問する
https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYGf7K180DFAVT
📖 に答える
これは繰り返し不可能なソートの問題です.1, 2, 3, ... 順番A C B...このように重複せずに選べばいいです.
backtrackingを行わずに再帰的に問題を解決するとO(n!)の時間複雑度nから15なので、15!はい.
130767468000は、1兆を超える大きなケースが現れ、逆追跡に減らすべきだ.
curを最後に回して、これまで求めていた最小生産費用よりも、現在求めている生産費用が大きいか等しいかであれば、決して答えにはならないので枝を切る.
📒 コード#コード#
def recur(cur, total): # 중복 없는 순열
global min_total
if total > min_total: # 가지치기
return
if cur == n:
min_total = min(min_total, total)
return
for i in range(n):
if visited[i] == 1:
continue
visited[i] = 1
recur(cur + 1, total + arr[cur][i])
visited[i] = 0
t = int(input())
for tc in range(1, t + 1):
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [0 for _ in range(n)] # 방문 표시
min_total = 100 * n
recur(0, 0)
print(f'#{tc} {min_total}')🔍 結果
Reference
この問題について([SWEA] 5209. [Python S/Wトラブルシューティング実施]5日間-最低生産コスト[D 3]), 我々は、より多くの情報をここで見つけました https://velog.io/@yunhlim/SWEA-5209.-파이썬-SW-문제해결-구현-5일차-최소-생산-비용-D3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol