Tìm số nhỏ nhất

Thảo luận trong 'ACM/Programming' bắt đầu bởi likehack, 26/07/19, 04:07 PM.

  1. likehack

    likehack Active Member

    Tham gia: 08/01/17, 09:01 PM
    Bài viết: 32
    Đã được thích: 3
    Điểm thành tích:
    8
    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ời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  2. krone

    krone Moderator Thành viên BQT

    Tham gia: 26/07/16, 03:07 PM
    Bài viết: 258
    Đã được thích: 135
    Điểm thành tích:
    43
    Bài này khoai nhỉ :D, mình có thử giải mà chưa có hướng nào ngoài giả định biến.
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  3. repott

    repott New Member

    Tham gia: Thứ bảy
    Bài viết: 2
    Đã được thích: 0
    Điểm thành tích:
    1
    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ời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  4. likehack

    likehack Active Member

    Tham gia: 08/01/17, 09:01 PM
    Bài viết: 32
    Đã được thích: 3
    Điểm thành tích:
    8
    sorry ban nhe, a1 -> an la cac so >=0, thank ban
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  5. repott

    repott New Member

    Tham gia: Thứ bảy
    Bài viết: 2
    Đã được thích: 0
    Điểm thành tích:
    1
    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)
     

    Các file đính kèm:

    Chỉnh sửa cuối: 25/08/19, 10:08 PM lúc 10:02 PM
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan