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

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

ซื้อของเล่นตัวแรก: K=50, count=1, เหลือ K=40 (50-10)
ซื้อของเล่นตัวที่สอง: K=40, count=2, เหลือ K=28 (40-12)
ซื้อของเล่นตัวที่สาม: K=28, count=3, เหลือ K=13 (28-15)
ตอนนี้ K < ราคาต่อไป (20) ดังนั้น 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 เกินงบ max count=1

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

อาเรย์ toyprice[] เก็บราคาของเล่น
ฟังก์ชัน maxToys(int price[], int N, int K) รับอาเรย์ราคา, ความยาว, และเงิน
toycount นับจำนวนของเล่นที่ซื้อได้ เริ่มต้น 0
spent ตรวจสอบเงินที่ใช้ไปจาก K
เรียงอาเรย์ price[] จากน้อยไปมากด้วย sort(price, price + N)
ลูปผ่าน price[] จากราคาต่ำสุด ถ้า spent + price[i] <= K ให้เพิ่ม toycount และ spent += price[i]
หากเกินงบ break เพราะอาเรย์เรียงแล้ว
คืนค่า toycount

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int maxToys(int price[], int N, int K) {
    int toycount = 0;
    int spent = 0;
    sort(price, price + N);
    for (int i = 0; i < N; i++) {
        if (spent + price[i] <= K) {
            spent += price[i];
            toycount++;
        } else
            break;
    }
    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