मान लीजिए हम एक बिलबोर्ड स्थापित कर रहे हैं और हम चाहते हैं कि इसकी ऊंचाई सबसे अधिक हो। बिलबोर्ड के दोनों तरफ दो स्टील सपोर्ट होंगे। प्रत्येक सपोर्ट की ऊंचाई समान होनी चाहिए। हमारे पास रॉड्स का एक संग्रह है जिन्हें एक साथ वेल्ड किया जा सकता है। हमें अपने बिलबोर्ड इंस्टॉलेशन की सबसे बड़ी संभव ऊंचाई ढूंढनी है। यदि हम बिलबोर्ड को सपोर्ट नहीं कर सकते, तो 0 वापस करें।
उदाहरण के लिए, यदि इनपुट [1,2,2,3,3,3,4] है, तो आउटपुट 9 होगा, क्योंकि हमारे पास [1,2,2,4] और [3,3,3] जैसे सबसेट हैं।
हल करने का दृष्टिकोण
हम दो सपोर्ट के बीच अंतर को ट्रैक करने के लिए डायनामिक प्रोग्रामिंग का उपयोग करते हैं:
dp[i][j] = पहले i रॉड्स का उपयोग करके अंतर j-5000 के साथ अधिकतम ऊंचाई
ऑफसेट 5000 नकारात्मक अंतर को संभालता है
प्रत्येक रॉड के लिए, तीन विकल्पों पर विचार करें: सपोर्ट 1 में जोड़ें, सपोर्ट 2 में जोड़ें, या छोड़ दें
dp टेबल को तदनुसार अपडेट करें
अंतिम उत्तर dp[n][5000] है (अंतर 0)
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int tallestBillboard(vector<int>& rods){
int sum = 0;
int n = rods.size();
int N = 2 * 5000;
vector<vector<int> > dp(n + 1, vector<int>(N + 1, -1));
dp[0][5000] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= N; j++) {
int x = rods[i];
if (j - x >= 0 && dp[i][j - x] != -1) {
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - x] + x);
}
if (j + x <= N && dp[i][j + x] != -1) {
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j + x]);
}
if (dp[i][j] != -1) {
dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
}
}
}
return dp[n][5000];
}
};
int main(){
Solution ob;
vector<int> v = {1,2,2,3,3,3,4};
cout << (ob.tallestBillboard(v));
return 0;
}
इनपुट
{1,2,2,3,3,3,4}
आउटपुट
9