Tối đa hóa lợi nhuận bằng cách bán tối đa M sản phẩm trong C++

Cho N sản phẩm, mỗi sản phẩm có giá vốn CP[i] và giá bán SP[i]. Nhiệm vụ: chọn tối đa M sản phẩm để bán sao cho lợi nhuận tổng lớn nhất.

Ví dụ

Input

N=6, M=4
CP[] = {1, 9, 5, 8, 2, 11}
SP[] = {1, 15, 10, 16, 5, 20}

Output – 28

Giải thích: Lợi nhuận từng SP: 0, 6, 5, 8, 3, 9. Chọn 4 lớn nhất: 9, 8, 6, 5 → Tổng = 28.

Thuật toán

1. Tính lợi nhuận profit[i] = SP[i] - CP[i] cho mỗi sản phẩm.
2. Sắp xếp mảng profit giảm dần.
3. Cộng M giá trị profit dương lớn nhất.
4. Dừng khi hết M sản phẩm hoặc profit ≤ 0.

Ví dụ code

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

int maxProfit(int N, int M, int Cp[], int Sp[]) {
    vector<int> profit(N);
    for (int i = 0; i < N; i++) {
        profit[i] = Sp[i] - Cp[i];
    }
    
    sort(profit.begin(), profit.end(), greater<int>());
    
    int total = 0;
    for (int i = 0; i < M && i < N; i++) {
        if (profit[i] > 0) total += profit[i];
        else break;
    }
    return total;
}

int main() {
    int N = 6, M = 4;
    int CP[] = {1, 9, 5, 8, 2, 11};
    int SP[] = {1, 15, 10, 16, 5, 20};
    cout << "Maximum Profit: " << maxProfit(N, M, CP, SP) << endl;
    return 0;
}

Kết quả

Maximum Profit: 28

Độ phức tạp: O(N log N) do sắp xếp. Có thể O(N) dùng nth_element hoặc heap size M.