Cắt que

Một que tính có chiều dài n. Một bảng khác cũng được cung cấp, trong đó có các kích thước và giá cả khác nhau cho từng kích thước. Xác định 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.

Giả sử f (n) sẽ trả về giá lớn nhất có thể sau khi cắt một hàng có độ dài n. Chúng ta có thể viết một cách đơn giản hàm f (n) như thế này.

f (n):=giá trị lớn nhất từ ​​giá [i] + f (n - i - 1), trong đó tôi nằm trong khoảng từ 0 đến (n ​​- 1).

Đầu vào và Đầu ra

Đầu vào :

Giá của các chiều dài khác nhau, và chiều dài của thanh. Ở đây độ dài là 8.

Đầu ra :

Lợi nhuận sau khi bán tối đa là 22.

Cắt que theo chiều dài 2 và 6. Lợi nhuận là 5 + 17 =22

Thuật toán

rodCutting(price, n)

Đầu vào: Bảng giá, số lượng các mức giá khác nhau trong danh sách.

Đầu ra: Lợi nhuận tối đa bằng cách cắt que.

Begin
   define profit array of size n + 1
   profit[0] := 0
   for i := 1 to n, do
      maxProfit := - ∞
      for j := 0 to i-1, do
         maxProfit := maximum of maxProfit and (price[j] + profit[i-j-1])
      done

      profit[i] := maxProfit
   done
   return maxProfit
End

Ví dụ

#include <iostream>
using namespace std;

int max(int a, int b) {
   return (a > b)? a : b;
}

int rodCutting(int price[], int n) {    //from price and length of n, find max profit
   int profit[n+1];
   profit[0] = 0;
   int maxProfit;

   for (int i = 1; i<=n; i++) {
      maxProfit = INT_MIN;    //initially set as -ve infinity
      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 << "Maximum Price: "<< rodCutting(priceList, rodLength);
}

Đầu ra

Maximum Price: 22