Chương trình C++ tìm lợi nhuận tối đa bán xe đỏ/xanh với xe chưa sơn

Mô tả bài toán

Cần bán p xe đỏ, q xe xanh. Kho có a xe đỏ, b xe xanh, c xe trắng (có thể sơn đỏ hoặc xanh). Giá các xe cho trước. Tối đa hóa tổng giá trị xe bán được.

Ví dụ

p=3,q=3,a=3,b=3,c=2, A={150000,200000,200000}, B={150000,120000,180000}, C={210000,160000,150000}. Đầu ra: 1100000.

Thuật toán (Tham lam + Tiền tố)

1. Sắp xếp A,B,C giảm dần.
2. Lấy p xe đỏ đắt nhất từ A, q xe xanh đắt nhất từ B → gộp vào mảng dp, sắp xếp giảm dần.
3. Tính tiền tố dp[i] = tổng i xe tốt nhất hiện có.
4. Thử thay thế i xe (1..min(c,p+q)) bằng i xe trắng đắt nhất: res = max(res, dp[p+q-i] + sum(C[0..i-1])).

Đoạn mã C++

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

int solve(int p,int q,int a,int b,int c,
          vector<int> A,vector<int> B,vector<int> C) {
    vector<int> dp(1,0);
    sort(A.rbegin(),A.rend());
    sort(B.rbegin(),B.rend());
    sort(C.rbegin(),C.rend());
    for(int i=0;i