คำชี้แจงปัญหา
ระบุไวน์ n รายการติดต่อกัน โดยจำนวนเต็มแสดงถึงต้นทุนของไวน์แต่ละชนิดตามลำดับ ในแต่ละปี คุณสามารถขายไวน์ตัวแรกหรือตัวสุดท้ายในแถวได้ ราคาของไวน์เพิ่มขึ้นเมื่อเวลาผ่านไป ให้กำไรขั้นต้นจากไวน์เป็น P1, P2, P3…Pn. ในปีที่ Y กำไรจากไวน์ ith จะเป็น Y*Pi ในแต่ละปี งานของคุณคือการพิมพ์จุดเริ่มต้นหรือจุดสิ้นสุดเพื่อระบุว่าควรขายไวน์ตัวแรกหรือตัวสุดท้าย คำนวณกำไรสูงสุดจากไวน์ทั้งหมดด้วย
ตัวอย่าง
If wine prices are {2, 4, 6, 2, 5} then output will be:
start end end start start
Maximum profit = 64 อัลกอริทึม
เราสามารถใช้โปรแกรมไดนามิกเพื่อแก้ปัญหานี้ได้ -
- แนวคิดคือการจัดเก็บการดำเนินการที่เหมาะสมที่สุดสำหรับแต่ละรัฐ และใช้เพื่อนำทางผ่านสถานะที่เหมาะสมที่สุดโดยเริ่มจากสถานะเริ่มต้น
ตัวอย่าง
#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;
} else {
sell[begin][end] = 1;
}
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
