Chương trình tìm lợi nhuận tối đa cắt thanh kim loại độ dài khác nhau trong C++

Giả sử có một thanh kim loại độ dài n. Ta cũng có một danh sách chứa kích thước và giá cho từng kích thước. Ta phải tìm giá tối đa bằng cách cắt thanh và bán chúng. Để có giá tốt nhất bằng cách cắt tại các vị trí khác nhau và so sánh giá sau khi cắt.

Vì vậy, nếu đầu vào là prices = [1, 5, 8, 9, 10, 17, 17, 20], n = 8, thì đầu ra sẽ là 22, vì cắt thanh thành độ dài 2 và 6. Lợi nhuận là 5 + 17 = 22.

Để giải quyết, ta làm theo các bước sau:

• Định nghĩa mảng profit kích thước n+1.
• profit[0] := 0
• với i := 1 đến n
  • maxProfit := âm vô cực
  • với j := 0 đến i-1
    • maxProfit := max(maxProfit, price[j] + profit[i - j - 1])
  • profit[i] := maxProfit
• trả về maxProfit

Hãy xem 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);
    return 0;
}

Đầu vào

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

Đầu ra

22