Lưu ý: Cách tối ưu nhất để sắp xếp các khối theo chiều từ trên đỉnh xuống dưới đáy là sắp xếp chúng theo chiều tăng dần cân nặng ~w~ và sức chịu nặng ~s~.

Xét ~2~ cách xếp ~2~ khối ~a~ và ~b~:

• Nếu như khối ~a~ ở vị trí đáy, ta có sức chịu nặng của toà tháp là: ~s_a - w_b~
• Nếu như khối ~b~ ở vị trí đáy, ta có sức chịu nặng của toà tháp là: ~s_b - w_a~

Hiển nhiên, ta sẽ chọn cách xếp để sức chịu nặng của tọa tháp lớn nhất có thể, là ~max(s_a - w_b, s_b - w_a)~. Dễ nhận thấy thay vì so sánh các giá trị ~(s_a - w_b)~, ~(s_b - w_a)~, ta có thể sắp xếp thứ tự của các khối bằng cách so sánh các giá trị ~(s_a + w_a)~, ~(s_b + w_b)~.

Để tối ưu hoá sức chịu nặng của toà tháp, chúng ta đặt khối có tổng ~s_i + w_i~ thấp hơn lên đỉnh. Đến đây, ta nhận thấy bài toán đã đưa về dạng bài toán quy hoạch động khá quen thuộc - Bài toán cái túi .

Nhận xét rằng giá trị của tháp phụ thuộc vào ~2~ yếu tố: có bao nhiêu khối đã được xét và trọng lượng của các khối. Do đó hướng giải sẽ là dùng mảng ~2~ chiều ~f[i][j]~: tổng giá trị lớn nhất của tháp khi xét ~i~ khối đầu và trọng lượng của tháp chưa vượt quá ~j~.

Tính ~f[i][j]~: khối đang xét là khối thứ ~i~ với trọng lượng của tháp bằng ~j~. Khi đó có ~2~ khả năng xảy ra:

• Nếu chọn khối ~i~ làm đáy tháp, tổng cân nặng các khối trên tháp trước đó không được quá ~j − w_i~. Tất nhiên ~j \le w_i + s_i~.
• Nếu không chọn khối ~i~, tổng cân nặng của tháp là như cũ (như lúc trước khi chọn khối ~i~): ~f[i − 1][j]~.

Tóm lại ta có:

~f[i][j] = max(f[i − 1][j − w[i]] + v[i], f[i − 1][j])~ Để tiết kiệm hơn nữa, ta có thể tối ưu hàm quy hoạch động trên hơn nữa bằng cách bỏ đi chiều biểu diễn số khối đã xét nhưng ta phải duyệt ngược từ cao xuống thấp, hãy thử suy nghĩ xem tại sao không thể duyệt từ thấp đến cao được.

Gọi ~dp[j]~ là giá trị tối đa mà tháp có thể đạt được với tổng cân nặng của tháp không vượt quá ~j~. Xét dãy theo chiều tăng dần đã sắp xếp ở trên, xét khối thứ ~i~, với ~w_i \le j \le w_i + s_i~, ta rút ra công thức sau:

~dp[j] = max(dp[j], dp[j - w[i]] + v[i])~ Kết quả cần tìm chính là ~max(dp[j])~ với ~j:0 \rightarrow max(s_i + w_i)~

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + 1;
const int MAX_W = 2e4 + 1;
long long dp[MAX_W];
int w[MAX_N], s[MAX_N], v[MAX_N], p[MAX_N];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;
    for(int i = 0; i < N; ++i) cin >> w[i] >> s[i] >> v[i];

    for(int i = 0; i < N; ++i) p[i] = i;

    sort(p, p + N, [&](const int &a, const int &b) {
        return w[a] + s[a] < w[b] + s[b];
    });

    for(int x = 0; x < N; ++x) {
        int i = p[x];
        for(int j = s[i] + w[i]; j >= w[i]; --j) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << *max_element(dp, dp + MAX_W) << endl;
}