โปรแกรม C++ หาจำนวนเงินสูงสุดที่สามารถทำได้จากการขายรถยนต์

สมมติว่ามีความต้องการขายรถสีแดงและสีน้ำเงิน บริษัทรถยนต์แห่งหนึ่งตัดสินใจขายรถยนต์สีแดงและรถสีน้ำเงิน q ในราคาต่างกัน ปัจจุบัน บริษัทมีรถสีแดงจำนวน 'a' หมายเลข 'b' ของรถยนต์สีน้ำเงิน และหมายเลข 'c' ของรถยนต์ที่ไม่มีสี (รถยนต์ยังไม่ได้ทำสี) ในสต็อก ค่าของรถยนต์แต่ละคันจะกำหนดเป็นอาร์เรย์ A, B และ C ดังนั้น บริษัทจึงต้องขายรถยนต์จำนวน p + q ในหนึ่งวันและต้องทำกำไรสูงสุดจากค่าดังกล่าว รถที่ไม่มีสีสามารถทาสีได้ทุกสี สีแดงหรือสีน้ำเงิน เราค้นพบจำนวนกำไรสูงสุดที่สามารถทำได้จากการขายรถยนต์

ดังนั้น หากอินพุตเป็น p =3, q =3, a =3, b =3, c =2, A ={150000, 200000, 200000}, B ={150000, 120000, 180000}, C ={ 210000, 160000, 150000} จากนั้นผลลัพธ์จะเป็น 1100000

บริษัทสามารถขายรถสีน้ำเงินมูลค่า 200,000, 200,000 และทาสีรถมูลค่า 210000 เป็นสีน้ำเงินได้ มูลค่ารวมที่ได้จากการขายรถสีน้ำเงินจะเท่ากับ 610000 นอกจากนี้ยังสามารถขายรถสีแดงมูลค่า 18000 และสีรถมูลค่า 160000 และ 150000 เพื่อให้ได้รวมเป็น 490000 มูลค่ากำไรทั้งหมดที่ได้รับจะเท่ากับ 610000 + 490000 =1100000

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

Define an array dp
sort the arrays A, B, and C
for initialize i := 0, when i < p, update (increase i by 1), do:
   insert A[i] at the end of dp
for initialize i := 0, when i < q, update (increase i by 1), do:
   insert B[i] at the end of dp
sort the array dp
reverse the array dp
for initialize i := 1, when i < size of dp, update (increase i by 1), do:
   dp[i] := dp[i] + dp[i - 1]
tmp := 0
res := last element of dp
for initialize i := 1, when i < (minimum of (c and p +q), update (increase i by 1), do:
   tmp := tmp + C[i - 1]
   res := maximum of (res and dp[p + q - i] + tmp)
return res

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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 < p; ++i)
      dp.push_back(A[i]);
   for(int i = 0; i < q; ++i) 
      dp.push_back(B[i]);
   sort(dp.begin(), dp.end());
   reverse(dp.begin() + 1, dp.end());
   for(int i = 1; i < (int)dp.size(); ++i)
      dp[i] += dp[i - 1];
   int tmp = 0;
   int res = dp.back();
   for(int i = 1; i <= min(c, p + q); ++i) {
      tmp += C[i - 1];
       res = max(res, dp[p + q - i] + tmp);
   }
   return res;
}
int main() {
   int p = 3, q = 3, a = 3, b = 3, c = 2;
   vector<int> A = {150000, 200000, 200000}, B = {150000, 120000, 180000}, C = {210000, 160000, 150000};
   cout<< solve(p, q, a, b, c, A, B, C);
   return 0;
}

อินพุต

3, 3, 3, 3, 2, {150000, 200000, 200000}, {150000, 120000, 180000}, {210000, 160000, 150000}