우리는 배열 형태의 장난감 가격과 손에 있는 금액 K가 제공됩니다. 목표는 최대 번호를 구입하는 것입니다. 그 양의 장난감. 배열의 각 요소는 하나의 장난감 가격이므로 없습니다. 장난감의 아니오입니다. 요소의. 가격 배열을 오름차순으로 정렬하여 더 낮은 가격의 최대 장난감을 먼저 구매한 다음 값비싼 장난감을 구매할 수 있도록 합니다.
입력
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
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 배열 toyrice[]는 장난감 가격을 저장합니다.
-
함수 maxToys( int price[], int N, int K ) 는 가격 배열, 길이 및 양을 취합니다.
-
toycount는 번호를 저장하는 데 사용됩니다. 구매할 수 있는 장난감의 수, 처음에는 0입니다.
-
변동 지출은 K에서 지출한 금액을 확인하는 데 사용됩니다.
-
sort(price, price + N);
를 사용하여 배열 price[]를 오름차순으로 정렬합니다. -
최저 가격, price[0]에서 최고가까지 배열 price[] 순회를 시작합니다.
-
사용된 장난감의 가격을 계속 추가하고 <=K인지 확인하고, 그렇다면 장난감 수를 늘립니다. 이는 이 장난감을 가져갈 수 있음을 의미합니다. 지출=지출+가격[i] 업데이트
-
드디어 toycount에 구매할 수 있는 장난감 수가 있습니다.
예시
#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