2014-01-16 101 views
0

考慮以下問題:如何在DP表中實現這個遞歸算法?

我們有一艘長度爲L的渡輪。這條渡輪用於在兩條河岸之間運輸車輛。渡輪有兩條車道,可以容納車輛。每輛車的長度爲l_i。每條車道上的車輛可以容納,使得它們不超過渡輪的長度。給定一列長度爲l_1, l_2, ..., l_n的車輛和長度爲L的渡輪,找出可容納的最大車輛數量。

請記住,車輛只能根據他們在隊列中的位置進入渡輪。例如,如果隊列中的車輛長度爲700, 600,且前方車輛較大,車道中剩餘的車位爲0, 400,則不能裝載較短的車輛而不是較長的車輛。

我能夠使用遞推關係來解決這個問題。讓solve(L1, L2, l_i, l_i+1, ..., l_n)返回長度爲l_i, l_i+1, ..., l_n的車輛的最大數量,該車輛可以容納在其兩條車道中的長度爲L1, L2的渡輪中。

function solve(L1, L2, l_i, l_i+1, ..., l_n) { 
    if (L1 - l_i > 0 and L2 - l_i > 0) { 
     return 1 + max(solve(L1 - l_i, L2, l_i+1, ..., l_n), solve(L1, L2 - l_i, l_i+1, ..., l_n)) 
    } else if (L1 - l_i > 0) { 
     return 1 + solve(L1 - l_i, L2, l_i+1, ..., l_n) 
    } else if (L2 - l_i > 0) { 
     return 1 + solve(L1, L2 - l_i, l_i+1, ..., l_n) 
    } else { 
     return 0 
    } 

} 

基本上這個算法計算放置車輛在渡口並在每個復發的最佳方式,它減去當前車輛的長度在隊列中從兩個通道的長度和通過這本身並計算兩種策略的最大值。如你所見,遞歸調用建立得相當快,程序效率不高。我如何使用動態編程方式實現相同的算法?

編輯:約束條件是,L是1,10,000和之間的每個轎廂的長度爲100和3000之間

回答

1

由於您已接受i汽車計算所有可能的渡輪配置。爲了處理車輛i+1,一組新配置是來自上一步的配置,其中新車在一個車道或另一個車道(在可能的情況下)。

一個單一的配置可以車道(之一的長度,因爲處理i汽車之後,你就會知道,兩個車道的長度之和爲L1 + L2 + ... + L_I。

所以,你可以保留的表可以是一組長度,或者如果你想要一個「表」,那麼你可以使用一個真/假值的數組並在適當位置更新(仔細地),這是在這個代碼中採用的方法。

def solve(L, car_lengths): 
    confs = [True] + [False] * L 
    S = 0 
    for i, c in enumerate(car_lengths): 
     S += c 
     for j in xrange(L, -1, -1): 
      if confs[j]: 
       if S - j > L: 
        confs[j] = False 
       if j + c <= L and S - j - c <= L: 
        confs[j + c] = True 
     if not any(confs): 
      return i 


print solve(9, (5, 2, 3, 4, 5, 5, 3, 4, 8)) 

的代碼是略微調皮因爲在就地更新:如果confs[j]爲1,則這意味着有可能有一個配置ù p前一輛車在j的第一車道。然後,如果添加新車(長度爲c),則可能的配置爲j(將車添加到第二車道)和j+c(將車添加到第一車道)。由於我們已經設置了conf[j],因此代碼會測試汽車是否不能添加到第二車道,並在此情況下清除conf[j]

下面是使用相同的方法,但有一套較不復雜的代碼。

def solve(L, car_lengths): 
    confs = set([0]) 
    S = 0 
    for i, c in enumerate(car_lengths): 
     S += c 
     confs |= set(j + c for j in confs) 
     confs = set(j for j in confs if j <= L and S - j <= L) 
     if not confs: 
      return i 


print solve(9, (5, 2, 3, 4, 5, 5, 3, 4, 8)) 
0

對於你的溶液,觀察到只有一個值在時間所指,我們可以簡單修改功能爲

function solve(int L1,int L2, index, int [] length){//index : what is the current index in the array length we are referring to 
} 

哪個會做同樣的事情。因此,我們可以很容易地拿出DP狀態DP[L1][L2][index]

的另一件事是,你可以要麼選擇要考慮到當前索引值或做這樣的事情

if(DP[L1][L2][index] != -1){//Need to initialize the DP table first 
    return DP[L1][L2][index]; 
} 
int max = 0; 
if(L1 >= length[index]){ 
    max = 1 + solve(L1 - length[index],L2,index + 1, length); 
} 
if(L2 >= length[index]){ 
    max = 1 + max(max,solve(L1 ,L2 - length[index],index + 1, length)); 
} 
max = max(max,solve(L1,L2,index + 1, length); 
移動到下一個索引

最後一次觀察的是L1和L2的順序並不重要,所以它可以用min,max(L1和L2之間的最小值,L1和L2之間的最大值)替代,這有助於減少步數爲DP。

+0

好的。因此,如果渡輪的長度是5000英尺,而轎廂的長度是2500,3000,1000,1000,1500,700,800,則該程序將生成一個5000 * 5000 * 7 3d陣列並計算其值。我對嗎?這將會非常低效,因爲我們將計算大量不需要的情況。有什麼方法可以減小數組的大小嗎? – Gerard

+0

@Gerard你應該在我的朋友的第一位提供這個約束。從未看到他們在你的post.Give DP解決方案不知道它的約束從來就不是一個好主意:) –

+0

@Gerard如果數組長度很小,你甚至可以考慮位掩模技術(在你的情況7),最好的事情在這裏提供了問題的鏈接:) –

1

通常在DP中,您將創建一個如答案Pham中所做的所有可能狀態的數組。根據OP的評論,在這種情況下這是不可行的。因此,保持一組可能的狀態直到當前的汽車可能會更好。

讓我們來創建狀態類(我在Java中這樣做,希望這很好)。我想保持簡潔,所以我不使用getters,只是公共領域。

class State { 
    public int lane1; 
    public int lane2;   

    public State(int lane1, int lane2) { 
     this.lane1 = lane1; 
     this.lane2 = lane2; 
    }   

    public boolean equals(Object o) { 
     if (o instanceof State) { 
      State other = (State) o; 
      return lane1 == other.lane1 && lane2 == other.lane2; 
     } else { 
      return false; 
     }    
    } 

    public int hashCode() { 
     return 31 * lane1 + lane2; 
    } 
} 

的equals和hashCode的實現都需要,因爲我希望把State對象在HashSet的,我們希望值等價,而不是參考等價。

有了這些狀態,你可以在車上循環。當考慮車輛i時,我們需要知道所有可能的狀態,直到車輛i-1,將車輛i添加到兩個車道並存儲兩個結果狀態(如果它們是可行的話)。代碼:

public int findMaxCars(int L, int[] len) {   
    Set<State> previousStates = new HashSet<>(); 

    // the only possible state when there are no cars on the ferry: 
    // both lanes have L remaining space 
    previousStates.add(new State(L, L)); 

    for (int i = 0; i < len.length; i++) { 
     Set<State> nextStates = new HashSet<>(); 

     for (State s : previousStates) { 
      if (s.lane1 - len[i] >= 0) // can fit car i in lane1 
       nextStates.add(new State(s.lane1 - len[i], s.lane2)); 
      if (s.lane2 - len[i] >= 0) // can fit car i in lane2 
       nextStates.add(new State(s.lane1, s.lane2 - len[i])); 
     } 

     if (nextStates.isEmpty()) { 
      // we couldn't fit car i anywhere, so the answer is: at most i cars 
      return i; 
     } else { 
      previousStates = nextStates; 
     } 
    } 
    // finished the loop, so all cars fit 
    return len.length; 
}