हमें खिलौनों की कीमतों के साथ एक सरणी और हाथ में एक राशि के रूप में दिया जाता है। लक्ष्य अधिकतम संख्या खरीदना है। उस राशि के खिलौनों की। सरणी का प्रत्येक तत्व एक खिलौने की कीमत है, इसलिए नहीं। खिलौनों की नहीं है। तत्वों की। हम कीमतों की सरणी को बढ़ते क्रम में क्रमबद्ध करेंगे ताकि कम कीमत के अधिकतम खिलौने पहले खरीदे जा सकें और उसके बाद महंगे खिलौने खरीदे जा सकें।
इनपुट
toyprices[]= { 10, 20, 12, 15, 50, 30 } K=50 आउटपुट
Maximum no. of toys that can be purchased : 3
स्पष्टीकरण - खिलौनों की कीमतों को आरोही क्रम में क्रमबद्ध करना - { 10, 12, 15, 20, 30 , 50 }
Take first toy: K=50, count=1, leftover K =40 ( 50-10 ) Take second toy: K=40, count=2, leftover K =28 ( 40-12 ) Take third toy: K=28, count=13, leftover K =13 ( 28-15 ) Now K< price of next toy 20 so count=3
इनपुट
toyprices[]= { 50,40,30,20,10 } K=25 आउटपुट
Maximum no. of toys that can be purchased : 1
स्पष्टीकरण − 25>10,20 लेकिन आप उनमें से केवल एक को 10+20=30 के रूप में ले सकते हैं। अधिकतम गणना=1
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक सरणी टॉयप्राइस [] खिलौनों की कीमतों को संग्रहीत करता है।
-
फंक्शन मैक्सटॉयज (इंट प्राइस [], इंट एन, इंट के) मूल्य सरणी, इसकी लंबाई और राशि लेता है
-
टॉयकाउंट का उपयोग नंबर को स्टोर करने के लिए किया जाता है। ख़रीदे जा सकने वाले खिलौनों की संख्या, प्रारंभ में 0.
-
K से कितना पैसा खर्च किया गया है, यह जांचने के लिए परिवर्तनीय खर्च का उपयोग किया जाता है।
-
सरणी मूल्य [] को सॉर्ट (कीमत, मूल्य + एन) का उपयोग करके आरोही क्रम में क्रमबद्ध करें;
-
सरणी मूल्य [] को न्यूनतम मूल्य, मूल्य [0] से उच्चतम तक ट्रैवर्स करना प्रारंभ करें।
-
खर्च में खिलौने की कीमत जोड़ते रहें और जांचें कि क्या <=के, यदि हां तो खिलौनों की गिनती बढ़ाएं। यानी यह खिलौना लिया जा सकता है। खर्च =खर्च + मूल्य [i] अपडेट करें।
-
अंत में टॉयकाउंट में कई खिलौने हैं जिन्हें खरीदा जा सकता है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int maxToys(int price[], int N, int K){
int toycount = 0;
int spent = 0; //money spent upto K only
// sort the prices so that minium prices are first
sort(price, price + N);
for (int i = 0; i < N; i++) {
if (spent + price[i] <= K){
spent = spent + price[i];
toycount++;
} else
break; //as array is sorted
}
return toycount;
}
int main(){
int budget = 100;
int toyprice[] = { 10, 120, 50, 11, 20, 100, 10, 90, 12, 15 };
int N = 10;
cout <<"Maximum no. of toys that can be purchased : "<< maxToys(toyprice, N, budget) ;
return 0;
} आउटपुट
Maximum no. of toys that can be purchased : 6