Tìm số nhỏ nhất

[likehack]

mình có 1 biểu thức:

P = a1x1 + a2x2 + a3x3 + ... + anxn

input gồm P và [x1, x2,x3,...,xn]

output là min của a1+a2+a3+...+an

ví dụ
24 = 20a1+8a2+a3
===> min(a1+a2+a3) = 3 với (a1 = 0; a2 = 3; a3 = 0)
thanks các bạn nhiều, suy nghĩ hoài k ra cách giải

 

mình có 1 biểu thức:

P = a1x1 + a2x2 + a3x3 + ... + anxn

input gồm P và [x1, x2,x3,...,xn]

output là min của a1+a2+a3+...+an

ví dụ
24 = 20a1+8a2+a3
===> min(a1+a2+a3) = 3 với (a1 = 0; a2 = 3; a3 = 0)
thanks các bạn nhiều, suy nghĩ hoài k ra cách giải

Bài này khoai nhỉ , mình có thử giải mà chưa có hướng nào ngoài giả định biến.

 

Mình có thử tìm cách giải cho bài toán bạn đưa ra. Tuy nhiên, cá nhân mình nhận thấy có lẽ bạn quên hoặc cho thiếu điều kiện của input và output.

Từ ví dụ bạn đưa: 20a1 + 8a2 + a3 = 24.
Mình tìm được một nghiệm là (a1, a2, a3) = (2, -2, 0) có tổng (a1 + a2 + a3) = (2 - 2 + 0) = 0.

Vậy nghiệm từ ví dụ của bạn là (0, 3, 0) không phải là nghiệm có tổng các phần tử bé nhất!

Do đó mình muốn biết điều kiện cụ thể là gì, ví dụ như input và output là số nguyên dương hay số thực...

 

Mình có thử tìm cách giải cho bài toán bạn đưa ra. Tuy nhiên, cá nhân mình nhận thấy có lẽ bạn quên hoặc cho thiếu điều kiện của input và output.

Từ ví dụ bạn đưa: 20a1 + 8a2 + a3 = 24.
Mình tìm được một nghiệm là (a1, a2, a3) = (2, -2, 0) có tổng (a1 + a2 + a3) = (2 - 2 + 0) = 0.

Vậy nghiệm từ ví dụ của bạn là (0, 3, 0) không phải là nghiệm có tổng các phần tử bé nhất!

Do đó mình muốn biết điều kiện cụ thể là gì, ví dụ như input và output là số nguyên dương hay số thực...

sorry ban nhe, a1 -> an la cac so >=0, thank ban

 

Mình có tìm được cách giải cho bài toán của bạn rồi nhé. Vì chứng minh dùng kí hiệu toán học mình không tiện viết ra ở đây, nên mình gửi file chứng minh đính kèm. Mình cũng xin tóm tắt lại nội dung chứng minh qua công thức ở phần dưới.

Đúc kết lại thì có 2 ý:

1. a1 = a2 = ... = an = P/(x1 + x2 + ... + xn) >= 0 (vì các số ai từ a1 đến an đều >= 0).
2. Min của S = a1 + a2 +...+ an = n x P/(x1 + x2 + ... + xn).

Ví dụ minh họa: 20a1 + 8a2 + a3 = 24

• a1 = a2 = a3 = P/(x1 + x2 + x3) = 24/(20 + 8 + 1) = 24/29.
• S = a1 + a2 + a3 = n x P/(x1 + x2 + x3) = 3 x 24/29 = 72/29 với (a1, a2, a3) = (24/29, 24/29, 24/29)