حل تمرین بازرگانی سوکرات و پسران کوئرا با پایتون
در این نوشته به روش حل یکی از سوالات برنامه نویسی وبسایت کوئرا میپردازیم.
حل تمرین بازرگانی سوکرات و پسران کوئرا با پایتون
سوکرات پس از استعفا از سمتهای دانشگاهی به دلیل استرس بالا، یک شرکت بازرگانی به نام «بازرگانی سوکرات و پسران» تأسیس کرد. در این شرکت N کار و N کارمند وجود دارد که هر کارمند میتواند هر یک از کارها را انجام دهد. اما هزینه انجام هر کار توسط هر کارمند متفاوت است. از آنجایی که سوکرات تا به امروز ضرر و زیانهای مالی زیادی دیده است میخواهد که همه کارهای شرکت با کمترین هزینه ممکن انجام شود. شما باید برنامهای بنویسید که به سوکرات بگوید برای هر کارمند کدام کار را انتخاب کند تا هزینه صرف شده برای کارمندان به حداقل برسد و اوضاع او کمی سر و سامان بیابد.
ورودی
- خط اول: تعداد کارمندان و کارها
- خط 2 تا N+1: ماتریس هزینه هر کارمند برای انجام هر کار. خط اول مربوط به هزینه های کارمند اول و خط دوم مربوط به هزینههای کارمند دوم است و…
خروجی
به تعداد N خط که خط iام بیانگر شماره کاری است که باید کارمند iام انجام دهد.
مثال
ورودی نمونه 1
4 9 2 7 8 6 4 3 7 5 8 1 8 7 6 9 4
خروجی نمونه 1
1 0 2 3
کد پایتون سوال تمرین بازرگانی سوکرات و پسران
import sys input = sys.stdin.read data = input().split() n = int(data[0]) cost = [] index = 1 for i in range(n): row = [] for j in range(n): row.append(int(data[index])) index += 1 cost.append(row) u = [0] * n v = [0] * n p = [-1] * n way = [-1] * n for i in range(n): links = [-1] * n mins = [float('inf')] * n visited = [False] * n marked_i = i marked_j = -1 j = 0 while True: j = -1 for j1 in range(n): if not visited[j1]: cur = cost[marked_i][j1] - u[marked_i] - v[j1] if cur < mins[j1]: mins[j1] = cur links[j1] = marked_j if j == -1 or mins[j1] < mins[j]: j = j1 delta = mins[j] for j1 in range(n): if visited[j1]: u[p[j1]] += delta v[j1] -= delta else: mins[j1] -= delta u[i] += delta visited[j] = True marked_j = j marked_i = p[marked_j] if marked_i == -1: break while True: if links[j] != -1: p[j] = p[links[j]] j = links[j] else: break p[j] = i assignment = [-1] * n for j in range(n): assignment[p[j]] = j for i in range(n): print(assignment[i])
منبع سوال: کوئرا
اگر نیاز به حل تمرینهای دیگری از کوئرا دارید در بخش نظرات همین نوشته برای ما بنویسید.
ارسال پاسخ