Trong bài toán này, chúng ta được đưa ra một danh sách bao gồm các mục và giá trị của chúng và một số nguyên k. Nhiệm vụ của chúng ta là tìm K mục có giá trị thấp nhất.
Mô tả sự cố: Chúng ta cần tìm k mục từ danh sách có giá trị thấp nhất.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: item-value ={{item1, 200}, {item2, 100}, {item3, 500}, {item4, 400}} k =2
Đầu ra: item1, item2
Giải thích:
Hai phần tử có giá trị nhỏ nhất là item1 với 200 và item2 với 100.
Phương pháp tiếp cận giải pháp
Một giải pháp cho vấn đề là tìm k mục có giá trị nhỏ nhất một cách tham lam. Đầu tiên chúng ta sẽ sắp xếp danh sách mục theo thứ tự giá trị tăng dần. Từ danh sách được sắp xếp này, chúng tôi sẽ tìm thấy k mặt hàng có giá trị nhỏ nhất.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
2 items with least value are Item : item4, value : 100 Item : item2, value : 150