C++でKの金額で購入できるおもちゃの数を最大化する

おもちゃの価格は配列の形で、金額Kが手元にあります。目標は最大数を購入することです。その量のおもちゃの。配列の各要素は1つのおもちゃの価格なので、違います。おもちゃのはありません。要素の。価格の配列を昇順で並べ替えて、価格の低い最大のおもちゃを最初に購入し、次に高価なおもちゃを購入できるようにします。

入力

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つだけを取ることができます。最大数=1

以下のプログラムで使用されているアプローチは次のとおりです

• 整数配列toyprice[]は、おもちゃの価格を格納します。

• 関数maxToys（int price []、int N、int K）は、価格配列、その長さ、および金額を受け取ります

• toycountは、番号を格納するために使用されます。購入できるおもちゃの数、最初は0。

• 使用済み変数は、Kから使用された金額を確認するために使用されます。

• sort（price、price + N）;

  を使用して、配列price[]を昇順で並べ替えます。

• アレイの価格[]を最低価格から最高価格[0]までトラバースし始めます。

• 使用済みのおもちゃの価格を追加し続け、<=Kかどうかを確認します。はいの場合は、おもちゃの数を増やします。これは、このおもちゃを購入できることを意味します。使用済み=使用済み+価格[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