2016-06-05 25 views
2

Ich versuche, bei DP besser zu werden und habe einige Übungsprobleme durchgemacht. Bitte werfen Sie einen Blick auf this one. Ich kann kaum eine Lösung dafür finden, aber es ist nur in Kleinigkeiten. Ich bin nicht in der Lage, sie miteinander zu verbinden und einen richtigen Algorithmus zu entwickeln. Wie würde man das durch dynamische Programmierung effizient lösen? P.S. Dies ist nicht Teil eines laufenden Wettbewerbs oder irgendeiner Art von Auftrag. Es ist nur ein Übungsproblem aus einem vergangenen Wettbewerb.Kann jemand eine dynamische Programmierlösung vorschlagen, um das zu lösen?

Kurze Beschreibung des Problems:

Sie sind gegeben 'n' Anzahl der Scheiben von Höhe und Radius variiert. Sie müssen den größtmöglichen Turm bauen, indem Sie diese Scheiben so verwenden, dass für jede dieser Scheiben sowohl der Radius als auch die Höhe kleiner sind als der Radius und die Höhe der darunter liegenden Scheibe.

Was ich versucht:

ich ein Array dp haben [1 .... n], wobei dp [i] (1 < = i < = n) speichert die Höhe des höchsten Turms können Sie baue nur mit den Discs im Bereich 1 .... i. Dann gibt es für die Disk i + 1 zwei Möglichkeiten. Ich benutze es entweder oder nicht. Also iteriere ich von 1 bis i und füge die Höhen aller Discs hinzu, deren Abmessungen nicht mit der Disc i + 1 in Konflikt stehen. Dann wähle ich das Größere aus dieser Summe + Höhe von Scheibe i + 1 und dp [i] und speichere es in dp [i + 1]. Offensichtlich funktioniert das in einigen Fällen nicht. Ich überprüfe nicht, ob irgendwelche der anderen Discs, die ich ausgewählt habe, sich untereinander widersprechen. Nicht sicher, ob es verständlich ist, aber das ist das Beste, was ich erklären kann.

+0

Bitte definieren Sie das Problem kurz, abgesehen von dem Link. Gib auch an, was du versucht hast. – sashas

+0

Aktualisiert die Frage. –

Antwort

2

Sie haben den richtigen Ansatz, den Sie nur brauchen, um das Paar von Höhen und Radius zu sortieren, sobald Sie dies getan haben, ist eine O (n^2) Lösung möglich.

Bei jedem Index können Sie das aktuelle Element basierend auf der Tatsache, dass das vorher ausgewählte Element ausgewählt wurde, entweder mit dem vorherigen Element 0 to i-1 für das aktuelle Element i vergleichen.

Ich habe einen einfachen rekursive DP Code in C++ geschrieben:

#include<bits/stdc++.h> 
using namespace std; 

int n; 
vector< pair<long long, long long> > val; 
long long dp[300][300]; 

long long solve(int idx, int prev){ 
    if(idx == n+1) return 0; 
    if(dp[idx][prev] != -1) return dp[idx][prev]; 
    //do not choose current element 
    long long ans = solve(idx+1, prev); 

    //try to choose current element 
    if(val[idx].first > val[prev].first && val[idx].second > val[prev].second){ 
     ans = max(ans, solve(idx+1, idx) + val[idx].second); 
    } 
    return dp[idx][prev] = ans; 
} 

int main(){ 
    int t;cin >> t; 
    while(t--){ 
     cin >> n; 
     long long rad, ht; 
     val.clear(); 
     val.push_back(make_pair(0, 0)); 
     for(int i = 0;i < n;i++) cin >> rad >> ht, val.push_back(make_pair(rad, ht)); 
     for(int i = 0;i < 300;i++) for(int j = 0;j < 300;j++) dp[i][j] = -1; 
     sort(val.begin(), val.end()); 
     cout << solve(1, 0) << endl; 
    } 
    return 0; 
} 
+1

@j_random_hacker nehme an, wenn die Eingabe ich habe ist (4, 4), (5, 5), (3, 3) wenn ich die Eingabe nicht sortieren würde, würde das nicht die Antwort als 9 geben, stattdessen sollte die Antwort nach mir sei 12, stimmt etwas mit dieser Logik nicht oder fehlt etwas? – uSeemSurprised

+0

Das stimmt. Ich nehme an, mit dem ich Schwierigkeiten habe: Höhe und Radius sind austauschbar (in jeder Hinsicht gleich behandelt), und wenn man sortiert, kann man nur * einen * den ersten Sortierschlüssel machen - also wenn die Korrektheit abhängt auf irgendwie gleichzeitig sortiert werden durch * beide *, wie kann der Algorithmus richtig sein, wenn eine Eingabe gegeben wird, in der diese gleichzeitige Sortierung nicht möglich ist? –

+1

@j_random_hacker sie sind nicht austauschbar, da wir versuchen, die Höhe zu maximieren, und wir tun dies nicht mit dem Radius. – uSeemSurprised

1

Da es sich um dynamische Programmierung Sie sehen müssen, wenn die Situation wiederholt. Wenn der Radius/die Höhe, die Sie verwenden dürfen, gleich ist, dann ist die Antwort dieselbe. Außerdem, da das Problem sagt, dass es "kleiner als" ist, müssen Sie sich keine Gedanken darüber machen, eine Disc zweimal zu benutzen. Da die gleiche Disc zweimal verwendet wird, ist dies automatisch ausgeschlossen.

int dp(int allowed_rad, int allowed_height){ 
    if(memo[allowed_rad][allowed_height] == true) //I alread have the answer 
     return dp[allowed_rad][allowed_height]; 
    memo[allowed_rad][allowed_height] = true; 

    dp[allowed_rad][allowed_height] = 0; //Initiallizing with zero 

    int ret = 0; 
    for(int i = 0; i < n; i++){ 
     if(rad[i] < allowed_rad && height[i] < allowed_height){ 
      int result = height[i] + dp(rad[i], height[i]); 
      if(result > ret) ret = result; 
     } 
    } 

    //it is possible that 0 is returned if I don't have any more option 
    return dp[allowed_rad][allowed_height] = ret; 
} 
Verwandte Themen