इस समस्या में, हमें एक सूची दी गई है जिसमें आइटम और उनके मान और एक पूर्णांक k है। हमारा काम सबसे कम मान वाले K आइटम ढूंढना है।
समस्या का विवरण: हमें सूची से k आइटम खोजने की जरूरत है जिनका मूल्य सबसे कम है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: आइटम-मान ={ {आइटम1, 200}, {आइटम2, 100}, {आइटम3, 500}, {आइटम4, 400}} के =2
आउटपुट: आइटम1, आइटम2
स्पष्टीकरण:
कम से कम मूल्य वाले दो तत्व हैं 200 के साथ आइटम 1 और 100 के साथ आइटम 2।
समाधान दृष्टिकोण
समस्या का समाधान कम से कम मूल्य वाली k वस्तुओं को लालच से खोजना है। हम पहले आइटम सूची को मूल्यों के आरोही क्रम में क्रमबद्ध करेंगे। इस क्रमबद्ध सूची से हमें k कम से कम मूल्य के आइटम मिलेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
bool compVal(pair<string, int> A, pair<string, int> B) {
if (A.second == B.second)
return A.first < B.first;
return A.second < B.second;
}
int main() {
int k = 2;
int n = 3;
vector<pair<string, int> > items;
items.push_back(make_pair("item1", 350));
items.push_back(make_pair("item2", 150));
items.push_back(make_pair("item3", 500));
items.push_back(make_pair("item4", 100));
sort(items.begin(), items.end(), compVal);
cout<<k<<" items with least value are \n";
for (int i = 0; i < min(n, k); ++i)
cout<<"Item : "<<items[i].first<<", value : "<<items[i].second<<endl;
return 0;
} आउटपुट
2 items with least value are Item : item4, value : 100 Item : item2, value : 150