เพิ่มจำนวนของเล่นที่สามารถซื้อได้ด้วยจำนวน K ใน C++

เราได้รับราคาของเล่นในรูปแบบของอาร์เรย์และจำนวน 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

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ราคาของเล่นอาร์เรย์จำนวนเต็ม[] ใช้เก็บราคาของของเล่น

• ฟังก์ชัน maxToys( int price[], int N, int K ) รับอาร์เรย์ราคา ความยาวและจำนวนของมัน

• toycount ใช้สำหรับเก็บหมายเลข ของของเล่นที่ซื้อได้เริ่มต้น 0.

• ตัวแปรที่ใช้ไปเช็คยอดใช้จ่ายจาก K.

• จัดเรียงราคาอาร์เรย์[]จากน้อยไปหามากโดยใช้การเรียงลำดับ(ราคา, ราคา + N);

• เริ่มสำรวจราคาอาร์เรย์[] จากราคาต่ำสุด ราคา[0] จนถึงสูงสุด

• เพิ่มราคาของของเล่นที่ใช้ไปและตรวจสอบว่า <=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