Chương trình tìm kiếm lợi nhuận tối đa bằng cách cắt thanh có độ dài khác nhau trong C ++

Giả sử chúng ta có một thanh có chiều dài n. Chúng tôi cũng có một danh sách, chứa các kích thước và giá cả khác nhau cho từng kích thước. Chúng tôi phải tìm giá tối đa bằng cách cắt thanh và bán chúng trên thị trường. Để có giá tốt nhất bằng cách cắt ở các vị trí khác nhau và so sánh giá sau khi cắt thanh.

Vì vậy, nếu đầu vào là giá =[1, 5, 8, 9, 10, 17, 17, 20], n =8, thì đầu ra sẽ là 22, bằng cách cắt thanh theo chiều dài 2 và 6. lợi nhuận là 5 + 17 =22.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định lợi nhuận mảng có kích thước:n + 1.

• lợi nhuận [0]:=0

• để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -

  • maxProfit:=âm vô cực

  • để khởi tạo j:=0, khi j

    • maxProfit:=tối đa của maxProfit và giá [j] + lợi nhuận [i - j - 1]

  • lợi nhuận [i]:=maxProfit

• return maxProfit

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
}

Đầu vào

{1, 5, 8, 9, 10, 17, 17, 20}, 8

Đầu ra

22