मान लीजिए कि हम एक बिलबोर्ड स्थापित कर रहे हैं और हम चाहते हैं कि इसकी ऊंचाई सबसे अधिक हो। बिलबोर्ड में दोनों तरफ स्टील के दो सपोर्ट होंगे। प्रत्येक समर्थन समान ऊंचाई का होना चाहिए। हमारे पास छड़ का एक संग्रह भी है जिसे एक साथ वेल्ड किया जा सकता है। इसलिए, यदि हमारे पास लंबाई 1, 2, और 3 की छड़ें हैं, तो हम लंबाई 6 का समर्थन करने के लिए उन्हें एक साथ जोड़ सकते हैं। हमें अपने बिलबोर्ड की स्थापना की सबसे बड़ी संभव ऊंचाई का पता लगाना होगा। अगर हम बिलबोर्ड का समर्थन नहीं कर सकते हैं, तो 0 लौटाएं।
इसलिए, यदि इनपुट [1,2,2,3,3,3,4] जैसा है, तो आउटपुट 9 होगा, क्योंकि हमारे पास [1,2,2,4] और [3,3, 3].
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
योग:=0, एन:=छड़ का आकार, एन:=2 * 5000
-
एक 2डी सरणी को परिभाषित करें dp(n + 1) x (N + 1, -1)
-
डीपी [0, 5000]:=0
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
इनिशियलाइज़ j :=0 के लिए, जब j <=N, अपडेट करें (j को 1 से बढ़ाएँ), करें -
-
x:=छड़[i]
-
अगर j - x>=0 और dp[i, j - x] -1 के बराबर नहीं है, तो -
-
dp[i + 1, j] =अधिकतम dp[i + 1, j] और dp[i, j - x] + x
-
-
अगर j + x <=N और dp[i, j + x] -1 के बराबर नहीं है, तो -
-
dp[i + 1, j] =अधिकतम dp[i + 1, j] और dp[i, j + x]
-
-
अगर dp[i, j] -1 के बराबर नहीं है, तो
-
dp[i + 1, j] =अधिकतम dp[i, j] और dp[i + 1, j]
-
-
-
-
वापसी डीपी [एन, 5000]
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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];
}
};
main(){
Solution ob;
vector<int> v = {1,2,2,3,3,3,4};
cout << (ob.tallestBillboard(v));
} इनपुट
{1,2,2,3,3,3,4} आउटपुट
9