資料結構
網路
關係型資料庫管理系統
作業系統
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+ 瀏覽量
廣告