Tối đa hóa số đồ chơi có thể mua với số tiền K trong C++

Chúng ta được cho giá các đồ chơi dưới dạng mảng và một số tiền K. Mục tiêu là mua số lượng đồ chơi tối đa với số tiền đó. Mỗi phần tử của mảng là giá của một đồ chơi, nên số đồ chơi là số phần tử. Chúng ta sẽ sắp xếp mảng giá theo thứ tự tăng dần để mua tối đa đồ chơi giá rẻ trước, sau đó đến đồ chơi đắt hơn.

Ví dụ

Đầu vào

toyprices[] = { 10, 20, 12, 15, 50, 30 } K = 50

Đầu ra

Số đồ chơi tối đa có thể mua: 3

Giải thích − Sắp xếp giá đồ chơi tăng dần: { 10, 12, 15, 20, 30, 50 }

Mua đồ đầu tiên: K=50, count=1, còn lại K=40 (50-10)
Mua đồ thứ hai: K=40, count=2, còn lại K=28 (40-12)
Mua đồ thứ ba: K=28, count=3, còn lại K=13 (28-15)
Bây giờ K < giá đồ tiếp theo 20 nên count=3

Đầu vào

toyprices[] = { 50, 40, 30, 20, 10 } K = 25

Đầu ra

Số đồ chơi tối đa có thể mua: 1

Giải thích − 25 > 10, 20 nhưng bạn chỉ có thể lấy một trong hai vì 10+20=30. Số lượng tối đa = 1.

Phương pháp sử dụng trong chương trình dưới đây

• Mảng số nguyên toyprice[] lưu giá đồ chơi.
• Hàm maxToys(int price[], int N, int K) nhận mảng giá, độ dài và số tiền.
• toycount lưu số đồ chơi có thể mua, khởi tạo 0.
• Biến spent kiểm tra số tiền đã chi từ K.
• Sắp xếp mảng price[] tăng dần bằng sort(price, price + N).
• Duyệt mảng price[] từ giá thấp nhất, price[0] đến cao nhất.
• Tiếp tục cộng giá đồ chơi vào spent và kiểm tra nếu <= K, nếu đúng tăng toycount. Nghĩa là đồ chơi này có thể lấy. Cập nhật spent = spent + price[i].
• Cuối cùng toycount có số đồ chơi có thể mua.

Ví dụ mã nguồn

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

int maxToys(int price[], int N, int K) { 
    int toycount = 0; 
    int spent = 0; // tiền chi tối đa K
    // sắp xếp giá để giá nhỏ nhất lên đầu
    sort(price, price + N); 
    for (int i = 0; i < N; i++) { 
        if (spent + price[i] <= K) { 
            spent = spent + price[i]; 
            toycount++; 
        } else 
            break; // vì mảng đã sắp xếp
    } 
    return toycount; 
} 

int main() { 
    int budget = 100; 
    int toyprice[] = { 10, 120, 50, 11, 20, 100, 10, 90, 12, 15 }; 
    int N = 10; 
    cout << "Số đồ chơi tối đa có thể mua: " << maxToys(toyprice, N, budget); 
    return 0; 
}

Kết quả

Số đồ chơi tối đa có thể mua: 6