สมมติว่าเรามีไม้เรียวยาว n เรายังมีรายการที่มีขนาดและราคาแตกต่างกันสำหรับแต่ละขนาด เราต้องหาราคาสูงสุดโดยการตัดแท่งแล้วขายในตลาด เพื่อให้ได้ราคาดีที่สุดโดยการตัดตำแหน่งต่างๆ และเปรียบเทียบราคาหลังตัดก้าน
ดังนั้น หากอินพุตมีค่าเท่ากับราคา =[1, 5, 8, 9, 10, 17, 17, 20], n =8 ผลลัพธ์จะเป็น 22 เช่นเดียวกับการตัดแท่งยาว 2 และ 6 กำไรคือ 5 + 17 =22
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดขนาดกำไรของอาร์เรย์:n+1
-
กำไร[0] :=0
-
สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
maxProfit :=ลบอินฟินิตี้
-
สำหรับการเริ่มต้น j :=0 เมื่อ j
-
maxProfit :=สูงสุดของ maxProfit และราคา[j] + profit[i − j − 1]
-
-
กำไร[i] :=maxProfit
-
-
คืนกำไรสูงสุด
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int max(int a, int b) {
return (a > b)? a : b;
}
int rodCutting(int price[], int n) {
int profit[n+1];
profit[0] = 0;
int maxProfit;
for (int i = 1; i<=n; i++) {
maxProfit = INT_MIN;
for (int j = 0; j < i; j++)
maxProfit = max(maxProfit, price[j] + profit[i-j-1]);
profit[i] = maxProfit;
}
return maxProfit;
}
int main() {
int priceList[] = {1, 5, 8, 9, 10, 17, 17, 20};
int rodLength = 8;
cout << rodCutting(priceList, rodLength);
} อินพุต
{1, 5, 8, 9, 10, 17, 17, 20}, 8 ผลลัพธ์
22
