数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律学用 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。
变量 spent 用于检查从 K 中花费了多少钱。
使用 sort(price, price + N); 将数组 price[] 按升序排序。
从最低价格 price[0] 开始遍历数组 price[]，直到最高价格。
不断将玩具的价格添加到 spent 中，并检查是否 <=K，如果是，则增加 toycount。这意味着可以购买这个玩具。更新 spent=spent+price[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
更新于: 2020年8月3日
2K+ 浏览量
广告