Tóm tắt đề bài

Tìm bộ ba ~x, y, z \geq 0, x + y + z \le S~ sao cho tích ~x^a \times y^b \times z^c~ lớn nhất. Giới hạn: ~1 \le S \le 1000, 0 \le a, b, c \le 1000~.

Chúng ta cần tìm cực trị của hàm ~f(x, y, z) = x^a \times y^b \times z^c~ theo giới hạn ~x + y + z = S~ (kết quả đạt tối đa khi tổng bằng ~S~) bằng cách sử dụng phương pháp nhân tử Lagrange.

Đặt ~L(x, y, z, \lambda) = x^a \times y^b \times z^c + \lambda (x + y + z - S)~ là hàm Lagrange.

Tiếp theo, lấy đạo hàm riêng của ~L~ theo ~x, y, z~ và ~\lambda~. Đặt các đạo hàm riêng này bằng ~0~ sẽ cho chúng ta các giá trị của ~x, y, z~ và ~\lambda~ tối ưu hóa ~f(x, y, z)~ theo ràng buộc ~g(x, y, z)~.

$$\displaystyle \begin{cases} \frac{\partial L}{\partial x} = ax^{a-1} \times y^b \times z^c -\lambda = 0 & (1) \\ \frac{\partial L}{\partial y} = ax^a \times y^{b-1} \times z^c -\lambda = 0 & (2) \\ \frac{\partial L}{\partial z} = ax^a \times y^b \times z^{c-1} -\lambda = 0 & (3) \\ \frac{\partial L}{\partial \lambda} = x + y + z - S = 0 & (4) \end{cases} $$

Từ ba phương trình ~(1) (2) (3)~, ta có ba vế bằng nhau (cùng bằng ~\lambda~):

~\lambda = ax^{a-1} \times y^b \times z^c = x^a \times by^{b-1} \times z^c = x^a \times y^b \times cz^{c-1}~

Chia tất cả các vế cho ~x^a \times y^b \times z^c~, ta được mối liên hệ ~\frac{a}{x} = \frac{b}{y} = \frac{c}{z}~

Dựa vào mối liên hệ và phương trình ~(4)~ ở trên ta có thể thấy tích các lũy thừa đạt giá trị tối đa khi ~(x, y, z)~ tỉ lệ với ~(a, b, c)~.

Thu được công thức tính cho từng giá trị ~x, y, z~ là:

x = S * a / (a + b + c), y = S * b / (a + b + c), z = S * c / (a + b + c);

Xét riêng trường hợp đặc biệt ~a + b + c = 0~ thì kết quả công thức trên trả về giá trị vô định nan do có mẫu số bằng ~0~. Cần phải xử lý riêng bằng việc đặt ~x = y = z = 0~, cho kết quả ~x^a \times y^b \times z^c = 0^0 \times 0^0 \times 0^0 = 1 \times 1 \times 1 = 1~ với mọi ~S \geq 1~ (~0^0~ được quy ước có giá trị ~1~ trong đại số)

Độ phức tạp thuật toán: ~\mathcal{O}(1)~.

Các bạn có thể tham khảo cài đặt của mình ở mục hướng dẫn giải của bài toán