मान लीजिए कि हमें एक सरणी गिरफ्तारी दी गई है जिसमें n धनात्मक पूर्णांक संख्याएँ हैं। हमें एक पूर्णांक संख्या j भी दी गई है। हमें जो कार्य करना है, वह है j संख्याओं को जोड़कर उन्हें एक संख्या में मिला देना। विलय की लागत हमारे द्वारा चुनी गई j संख्याओं के योग के बराबर है। हमें इस मर्जिंग ऑपरेशन के लिए न्यूनतम संभव लागत का पता लगाना होगा।
इसलिए, यदि इनपुट arr =[2, 5, 6, 2, 3, 1, 3], j =4 जैसा है, तो आउटपुट 31 होगा।
2, 3, 1, 3 को मर्ज करने की लागत 2 + 3 + 1 + 3 =9 के बराबर है।
मर्ज ऑपरेशन के बाद का ऐरे [2, 5, 6, 9] बन जाता है। दूसरे मर्ज ऑपरेशन की लागत 2 + 5 + 6 + 9 =22 के बराबर है। इसलिए, मर्ज ऑपरेशन की कुल लागत 22 + 9 =31 हो जाती है। यह न्यूनतम विलय लागत है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n :=गिरफ्तारी का आकार
- यदि (n-1) mod (j-1) 0 के बराबर नहीं है, तो −
- वापसी -1
- एक सरणी अस्थायी परिभाषित करें(n + 1)
- इनिशियलाइज़ करने के लिए i :=n-1, जब i>=0, अपडेट करें (i से 1 घटाएं), −
- करें
- temp[i] :=arr[i] + temp[i + 1]
- एक 2डी सरणी को परिभाषित करें dynArr क्रम n x n
- इनिशियलाइज़ k :=j के लिए, जब k <=n, अपडेट करें (k को 1 से बढ़ाएँ), करें -
- इनिशियलाइज़ le :=0, rg :=k-1 के लिए, जब rg
- dynArr[le, rg] :=inf
- इनिशियलाइज़ i :=le के लिए, जब i
- dynArr[le, rg] :=न्यूनतम (dynArr[le, rg] और dynArr[le, i] + dynArr[i + 1, rg])
- यदि (rg - le) mod (j-1) 0 के समान है, तो −
- dynArr[le, rg] :=dynArr[le, rg] + temp[le] - temp[rg + 1]
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& arr, int j) {
int n = arr.size();
if ((n - 1) % (j - 1) != 0) return -1;
vector<int> temp(n + 1);
for (int i = n - 1; i >= 0; i--) {
temp[i] = arr[i] + temp[i + 1];
}
vector<vector<int>> dynArr(n, vector<int>(n));
for (int k = j; k <= n; k++) {
for (int le = 0, rg = k - 1; rg < n; le++, rg++) {
dynArr[le][rg] = INT_MAX;
for (int i = le; i < rg; i += j - 1) {
dynArr[le][rg] = min(dynArr[le][rg], dynArr[le][i] + dynArr[i + 1][rg]);
}
if ((rg - le) % (j - 1) == 0) {
dynArr[le][rg] += temp[le] - temp[rg + 1];
}
}
}
return dynArr[0][n - 1];
}
int main() {
vector<int> arr = {2, 5, 6, 2, 3, 1, 3};
cout<< solve(arr, 4) <<endl;
return 0;
} इनपुट
{2, 5, 6, 2, 3, 1, 3}, 4 आउटपुट
31