กำไรสูงสุดจากการขายไวน์ใน C++

ข้อความปัญหา

ได้รับไวน์ n ขวดเรียงเป็นแถว พร้อมค่าตัวเลขแทนราคาของแต่ละขวด ทุกปีคุณสามารถขายขวดแรกหรือขวดสุดท้ายของแถวได้ ราคาไวน์เพิ่มขึ้นตามเวลา ให้กำไรเริ่มต้นเป็น P1, P2, P3...Pn ในปีที่ Y กำไรจากไวน์ขวดที่ i จะเป็น Y*Pi สำหรับแต่ละปี ให้พิมพ์ "start" หรือ "end" แทนว่าควรขายขวดแรกหรือขวดสุดท้าย และคำนวณกำไรสูงสุดจากไวน์ทั้งหมด

ตัวอย่าง

ถ้าราคาไวน์คือ {2, 4, 6, 2, 5} ผลลัพธ์จะเป็น:
start end end start start
Maximum profit = 64

อัลกอริทึม

เราสามารถใช้การเขียนโปรแกรมแบบไดนามิก (Dynamic Programming) เพื่อแก้ปัญหานี้ -

• แนวคิดคือเก็บการกระทำที่เหมาะสมสำหรับแต่ละสถานะ และใช้ข้อมูลนั้นนำทางผ่านสถานะที่เหมาะสมเริ่มจากสถานะเริ่มต้น

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

#include <bits/stdc++.h>
using namespace std;
#define N 1000
int dp[N][N];
int sell[N][N];

int maxProfitUtil(int price[], int begin, int end, int n) {
    if (dp[begin][end] != -1) {
        return dp[begin][end];
    }
    int year = n - (end - begin);
    if (begin == end) {
        return year * price[begin];
    }
    int x = price[begin] * year + maxProfitUtil(price, begin + 1, end, n);
    int y = price[end] * year + maxProfitUtil(price, begin, end - 1, n);
    int ans = max(x, y);
    dp[begin][end] = ans;
    if (x >= y) {
        sell[begin][end] = 0; // start
    } else {
        sell[begin][end] = 1; // end
    }
    return ans;
}

int maxProfit(int price[], int n) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dp[i][j] = -1;
        }
    }
    int ans = maxProfitUtil(price, 0, n - 1, n);
    int i = 0, j = n - 1;
    while (i <= j) {
        if (sell[i][j] == 0) {
            cout << "start ";
            i++;
        } else {
            cout << "end ";
            j--;
        }
    }
    cout << endl;
    return ans;
}

int main() {
    int price[] = { 2, 4, 6, 2, 5 };
    int n = sizeof(price) / sizeof(price[0]);
    int ans = maxProfit(price, n);
    cout << "Maximum profit = " << ans << endl;
    return 0;
}

ผลลัพธ์

start end end start start
Maximum profit = 64

คำอธิบาย

โปรแกรมใช้ DP แบบ Top-down with Memoization ตัวแปร dp[begin][end] เก็บกำไรสูงสุดจากช่วง [begin, end] และ sell[begin][end] เก็บการตัดสินใจว่าขายขวดไหน (0=start, 1=end)

ปีที่ขาย (year) คำนวณจาก n - (end - begin) ซึ่งจะเพิ่มขึ้นเมื่อช่วงแคบลง