在編程競賽中需要關於問題集的幫助

我參加了我的國家的本地編程比賽。比賽的名稱是「ACM-ICPC 2013年全國比賽」。
比賽已於2013-10-13 15:00:00（格林威治標準時間+7）結束，我仍然對其中一個問題感到好奇。
你可以找到問題的原始版本here。在編程競賽中需要關於問題集的幫助

簡要說明問題：
有，應該在幾個「服務器」（計算機）進行一組「工作」（任務）中。
每個作業應嚴格從開始時間S _我執行結束時間E _我
每個服務器只能一次執行一個任務。
（複雜的事情發生在這裏）服務器從一個工作切換到另一個需要一些時間。
如果一臺服務器完成工作j _X，然後開始工作j _Ÿ它需要一箇中場休息時間T _X，Y工作j之後_X完成。這是服務器清理作業所需的時間J _x和加載作業J _y。
換句話說，工作j _ý可以工作j之後運行_X當且僅如果E _X + T _的x，y≤小號_ÿ。

問題是要計算完成所有工作所需的最少服務器數量。

例子：
例如，讓有3個項目

S(1) = 3 and E(1) = 6 
S(2) = 10 and E(2) = 15 
S(3) = 16 and E(3) = 20 
T(1,2) = 2, T(1,3) = 5 
T(2,1) = 0, T(2,3) = 3 
T(3,1) = 0, T(3,2) = 0

在這個例子中，我們需要2臺服務器：

Server 1: J(1), J(2) 
Server 2: J(3)

樣品輸入：
短解釋：第一個3是測試用例的數量，其次是作業數量（第二個3意味着對於情況1有3個作業），然後是E _i和S _i，則T矩陣（大小等於數量工作）。

樣本輸出：

Case #1: 2 
Case #2: 1 
Case #3: 4

個人評論：
可以被表示爲圖矩陣所需要的時間，所以我假定這是一個向無環圖的問題。
我到目前爲止嘗試的方法是蠻力和貪婪，但得到了錯誤的答案。（不幸的是我沒有我的代碼了）
也許可以通過動態編程來解決，但我不確定。
我真的不清楚如何解決這個問題。
所以一個簡單的提示或洞察力將對我非常有幫助。

來源

2013-10-18 topher

我是比較新的堆棧溢出。我想問一下這樣的問題是不恰當的還是被認爲是偏離主題的。 – topher

您是否試圖將此模型作爲最大流量最小成本問題進行建模？ - 我相信這是要走的路。 – Skeen

@Skeen，謝謝你的見解，我以前沒有嘗試過.. – topher

你可以通過計算maximum matching in a bipartite graph來解決這個問題。

這個想法是你試圖將工作結束時間與工作開始時間相匹配。

匹配的結束時間x與開始時間y意味着相同的服務器將執行作業x和作業y。

您需要的服務器數量將對應於不匹配的開始時間的數量（因爲這些作業中的每一個都需要新的服務器）。使用NetworkX

例Python代碼：

import networkx as nx 
G=nx.DiGraph() 

S=[3,10,16] # start times 
E=[6,15,20] # end times 
T = [ [0, 2, 5], 
     [0, 0, 3], 
     [0, 0, 0] ] # T[x][y] 
N=len(S) 

for jobx in range(N): 
    G.add_edge('start','end'+str(jobx),capacity=1) 
    G.add_edge('start'+str(jobx),'end',capacity=1) 
    for joby in range(N): 
     if E[jobx]+T[jobx][joby] <= S[joby]: 
      G.add_edge('end'+str(jobx),'start'+str(joby),capacity=1) 

print N-nx.max_flow(G,'start','end')

來源

2013-10-18 17:54:46

在編程競賽中需要關於問題集的幫助

回答

相關問題