इस लेख में, हम n संख्याओं के दिए गए सरणी को पुनर्व्यवस्थित करने की समस्या पर चर्चा करेंगे। मूल रूप से, हमें सरणी से तत्वों का चयन करना होगा। प्रत्येक तत्व का चयन करने के लिए, हमें कुछ बिंदु मिलते हैं जिनका मूल्यांकन वर्तमान तत्व के मूल्य से किया जाएगा * वर्तमान तत्व से पहले चुने गए कई तत्व। अधिकतम अंक प्राप्त करने के लिए आपको तत्वों का चयन करना चाहिए। उदाहरण के लिए -
Input : arr[ ] = { 3, 1, 5, 6, 3 }
If we select the elements in the way it is given, our points will be
= 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4
= 41
To maximize the points we have to select the elements in order { 1, 3, 3, 5, 6 }
= 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4
= 48(maximum)
Output : 48
Input : arr[ ] = { 2, 4, 7, 1, 8 }
Output : 63 समाधान खोजने के लिए दृष्टिकोण
उदाहरण को देखते हुए, हमें वह अधिकतम अंक प्राप्त करने के लिए मिला, और हमें सबसे छोटे से सबसे बड़े तत्वों का चयन करने की आवश्यकता है। समाधान खोजने का तरीका है,
- दिए गए सरणी को आरोही क्रम में क्रमबद्ध करें।
- इंडेक्स 0 से अंत तक तत्वों को चुनना शुरू करें।
- प्रत्येक तत्व को चुनने से प्राप्त अंकों की गणना करें।
उदाहरण
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main () {
int arr[] = { 2, 4, 7, 1, 8 };
int n = sizeof (arr) / sizeof (arr[0]);
// sorting the array
sort (arr, arr + n);
int points = 0;
// traverse the array and calculate the points
for (int i = 0; i < n; i++) {
points += arr[i] * i;
}
cout << "Maximum points: " << points;
return 0;
} आउटपुट
Maximum points: 63
उपरोक्त कोड की व्याख्या
यह C++ कोड समझने में आसान है। पहले हम सरणी को सॉर्ट कर रहे हैं और फिर लूप के लिए उपयोग करके सरणी को पार करते हैं और शुरुआत से अंत तक प्रत्येक तत्व का चयन करके प्राप्त अंकों की गणना करते हैं।
निष्कर्ष
इस लेख में, हम अधिकतम अंक प्राप्त करने के लिए एक सरणी में तत्व के चयन की समस्या पर चर्चा करते हैं जहां अंक की गणना i * arr [i] द्वारा की जाती है। हम इस समस्या को हल करने और अधिकतम अंक प्राप्त करने के लिए लालची दृष्टिकोण लागू करते हैं। ऐसा करने के लिए सी ++ कोड पर भी चर्चा करें, हम इस कोड को सी, जावा, पायथन इत्यादि जैसी किसी अन्य भाषा में लिख सकते हैं। आशा है कि आपको यह लेख उपयोगी लगेगा।