以C ++的数量K最大化可以购买的玩具数量

我们得到的玩具价格为数组形式，手中的数量为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

以下程序中使用的方法如下

• 整数数组toyprice []存储玩具的价格。

• 函数maxToys（int price []，int N，int K）获取价格数组，其长度和金额

• toycount用于存储编号。可以购买的玩具数量，最初为0。

• 花费的变量用于检查从K花费了多少钱。

• 使用sort（price，price + N）以升序对数组price []进行排序。

• 从最小价格，价格[0]到最高价格开始遍历数组价格[]。

• 继续增加已花费玩具的价格，并检查是否<= K，如果是，则增加toycount。这意味着该玩具可以被拿走。更新支出=消费+价格[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(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