home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

เพิ่มกำไรสูงสุดจากการขายสินค้าสูงสุด M ชิ้นใน C++

งานคือคำนวณกำไรสูงสุดจากการขายสินค้าสูงสุด M ชิ้น จากทั้งหมด N ชิ้น กำหนดราคาทุน (CP[]) และราคาขาย (SP[]) ของแต่ละชิ้น

ตัวอย่าง

ตัวอย่างที่ 1

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

กำไรแต่ละชิ้น: {0, 6, 5, 8, 3, 9}

เลือก 4 ชิ้นกำไรมากสุด: 9, 8, 6, 5 → รวม = 28

Output: 28

ตัวอย่างที่ 2

Input: N=3, M=2, CP[]={10,20,30}, SP[]={19,22,38}

กำไร: {9, 2, 8}

เลือก 2 ชิ้น: 9, 8 → รวม = 17

Output: 17

แนวทางแก้ปัญหา (Greedy)

  1. คำนวณกำไรแต่ละชิ้น: profit[i] = SP[i] - CP[i]
  2. เรียงกำไรจากมากไปน้อย (descending)
  3. รวมกำไร M อันดับแรกที่ > 0 (ข้ามกำไรติดลบ/ศูนย์)

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

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

long long maxProfit(int N, int M, const vector<int>& CP, const vector<int>& SP) {
    vector<long long> profit(N);
    for (int i = 0; i < N; i++) {
        profit[i] = (long long)SP[i] - CP[i];
    }
    
    sort(profit.begin(), profit.end(), greater<long long>());
    
    long long 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;
    vector<int> CP = {1, 9, 5, 8, 2, 11};
    vector<int> SP = {1, 15, 10, 16, 5, 20};
    
    cout << "Maximum Profit: " << maxProfit(N, M, CP, SP) << endl;
    return 0;
}

ผลลัพธ์

Maximum Profit: 28

กรณีพิเศษ

  • M > N: ขายได้สูงสุด N ชิ้น (ลูปมี i < N)
  • กำไรติดลบ: ไม่ควรขาย (break เมื่อเจอ ≤ 0)
  • กำไรเป็น 0: ขายหรือไม่ขายก็ได้ (โค้ดข้างบน break ที่ ≤ 0)

ความซับซ้อน

  • เวลา: O(N log N) – จากการเรียงลำดับ
  • พื้นที่: O(N) – เก็บอาร์เรย์กำไร

ขยายความ: หากมี constraint เพิ่มเติม

หากมีเงื่อนไข เช่น "ต้องขายอย่างน้อย 1 ชิ้น" หรือ "มีงบประมาณจำกัด" จะกลายเป็น Knapsack problem ต้องใช้ Dynamic Programming แทน