Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: Bài toán về Quy Hoạch Động

  1. #1
    Ngày gia nhập
    05 2016
    Nơi ở
    Rạch giá
    Bài viết
    15

    Mặc định Bài toán về Quy Hoạch Động

    Hi mọi người... Lại là em đây... Hôm qua dở toán nay chắc dở thêm vụ tính tiền @@
    Lang mang v đủ òi... Chắc e vô thẳng đề bài đây.

    Em vẫn ko hiểu số b là như thế nào ạ??
    Và số a em làm 5 dòng for để chạy nhưng kết quả tầm 10s nó báo về press any key to continue chứ ko có ra bất kì kết quả nào @@
    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		fail.jpg
Lần xem:	13
Size:		79.0 KB
ID:		52081

  2. #2
    Ngày gia nhập
    07 2011
    Bài viết
    465

    viết giải thích dài dòng lắm

    gọi số cách thối tiền là w(n, V) với:
    - n là số tiền cần thối, ví dụ 15,
    - V là mảng chứa mệnh giá tiền, ví dụ [10,5,2]
    thì với đệ quy phải tìm cách đi tới w(n, V) với bước đi nhỏ nhất. Ở đây số cách thối 15 đồng có thể hiểu là bằng số cách thối 13 đồng (thêm 2 đồng nữa là thành 15). Nhưng chưa hết, vì với cách tính này thì 15 đồng tiền thối lúc nào cũng có tờ 2 đồng, vì vậy còn phải đếm các lần thối ko cần tờ 2 đồng nữa, hay w(15, [10,5,2]) = w(13, [10,5,2]) + w(15, [10,5]). Ở đây chỉ cần xét 1 loại mệnh giá thôi vì các mệnh giá kia sẽ được xử lý trong w(15, [10,5]) hay w(13, [10,5,2]).

    để viết công thức tổng quát thì cần thêm 1 biến m nữa, là số lượng tờ tiền trong V. w(n, V) chuyển thành W(n, V, m). Viết W(15, [10,5,2], 3) hiểu là w(15, [10,5,2]); W(15, [10,5,2], 2) hiểu là w(15, [10,5]). Quy ước thêm nữa V[1] là mệnh giá đầu tiên trong V, V[m] là mệnh giá cuối cùng.

    vậy ta có công thức đệ quy tổng quát: W(n, V, m) = W(n - V[m], V, m) + W(n, V, m-1)

    đệ quy thì phải có điều kiện dừng, hay base cases. Điều kiện dừng ở đây là
    - nếu n = 0, thì W(0, V, m) = 1
    - nếu n < 0, thì W(n, V, m) = 0
    - nếu n > 0 và m < 1, thì W(n, V, m) = 0

    code C++14:
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. using IntArray = std::vector<int>;
    5.  
    6. int W(int n, const IntArray& V, int m)
    7. {
    8.     if (n == 0) return 1;
    9.     if (n < 0 || m < 1) return 0;
    10.     return W(n - V[m-1], V, m) + W(n, V, m-1);
    11. }
    12.  
    13. int main()
    14. {
    15.     IntArray V{50,20,10,5,2};
    16.     std::cout << W(325, V, V.size()) << "\n";
    17.     std::cout << W(876, V, V.size()) << "\n";
    18.     std::cout << W(3, V, V.size()) << "\n";
    19. }

    cách này hơi chậm vì là đệ quy. Muốn nhanh hơn thì xài quy hoạch động, nói đơn giản là lưu lại các giá trị đã tính rồi để ko phải tính lại như đệ quy nữa.

    với quy hoạch động thì đi ngược lại từ nhỏ lên. Ở đây n tối đa là 1000 (10 triệu, mà là bội của 10 ngàn, nên chỉ có 1000 giá trị từ 1 tướng ứng với 10 ngàn tới 1000 tương ứng với 10 triệu), nên làm hẳn cái mảng 1000+1 phần tử luôn (thêm số 0), rồi đi từ nhỏ tới lớn. Kiểu na ná như Fibonacci ấy. Fibonacci đệ quy là F(n) = F(n-1) + F(n-2), thì thay vì đi từ F(1000) xuống F(999), F(998), F(997), v.v... thì ta có thể đi từ F(0) F(1) F(2) lên F(1000).

    ở đây khó hơn vì W(n, V, m) có tới 2 giá trị thay đổi là n và m. Cách giải là giữ nguyên 1 giá trị, ở đây là m, rồi tính W với n từ 0 tới 1000. Sau đó tăng m lên 1 đơn vị, rồi tính lại W từ 0 tới 1000, v.v... tới khi m = size(V).

    với m ko đổi, ta có W(n, V, m) = W(n, V, m) + W(n - V[m], V, m). Sở dĩ phải cộng dồn là vì m thay đổi, nên phần xanh lá thực chất chính là từ m cũ, hay là W(n, V, m-1).
    ví dụ n = 15, V = [10,5,2]. Ta tạo mảng p[0..15] gồm 16 phần tử, p[0] = 1 vì có đúng 1 cách thối 0 đồng:
         0  1  2  3  4  5  6  7   8  9 10 11 12 13 14 15
    m=0  1  0  0  0  0  0  0  0  0   0  0  0  0  0  0  0


    với m = 1, bắt đầu từ p[10] tới p[15], gán p[i] += p[i-10]
         0  1  2  3  4  5  6  7   8  9 10 11 12 13 14 15
    m=1  1  0  0  0  0  0  0  0  0   0  1  0  0  0  0  0


    với m = 2, bắt đầu từ p[5] tới p[15], gán p[i] += p[i-5]
         0  1  2  3  4  5  6  7   8  9 10 11 12 13 14 15
    m=2  1  0  0  0  0  1  0  0  0  0  2  0  0  0  0   2


    với m = 3, bắt đầu từ p[2] tới p[15], gán p[i] += p[i-2]
         0  1  2  3  4  5  6  7   8  9 10 11 12 13 14 15
    m=3  1  0  1  0  1  1  1  1  1  1  3  1   3  1  3  3


    code C++14:
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. using IntArray = std::vector<int>;
    5.  
    6. auto Wdp(int n, const IntArray& V)
    7. {
    8.     IntArray p(n+1, 0);
    9.     p[0] = 1;
    10.     for (int m = 0; m < V.size(); ++m)
    11.         for (int i = V[m]; i <= n; ++i)
    12.             p[i] += p[i-V[m]];
    13.     return p;
    14. }
    15.  
    16. int main()
    17. {
    18.     IntArray V{50,20,10,5,2};
    19.     auto p = Wdp(1000, V);
    20.     std::cout << p[325] << "\n";
    21.     std::cout << p[876] << "\n";
    22.     std::cout << p[3] << "\n";
    23. }

    code có 6-7 dòng mà giải thích thì dài dòng ~.~
    Đã được chỉnh sửa lần cuối bởi INTP : 12-03-2017 lúc 12:37 AM.

  3. #3
    Ngày gia nhập
    05 2016
    Nơi ở
    Rạch giá
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi INTP Xem bài viết
    viết giải thích dài dòng lắm

    gọi số cách thối tiền là w(n, V) với:
    - n là số tiền cần thối, ví dụ 15,
    - V là mảng chứa mệnh giá tiền, ví dụ [10,5,2]
    thì với đệ quy phải tìm cách đi tới w(n, V) với bước đi nhỏ nhất. Ở đây số cách thối 15 đồng có thể hiểu là bằng số cách thối 13 đồng (thêm 2 đồng nữa là thành 15). Nhưng chưa hết, vì với cách tính này thì 15 đồng tiền thối lúc nào cũng có tờ 2 đồng, vì vậy còn phải đếm các lần thối ko cần tờ 2 đồng nữa, hay w(15, [10,5,2]) = w(13, [10,5,2]) + w(15, [10,5]). Ở đây chỉ cần xét 1 loại mệnh giá thôi vì các mệnh giá kia sẽ được xử lý trong w(15, [10,5]) hay w(13, [10,5,2]).

    để viết công thức tổng quát thì cần thêm 1 biến m nữa, là số lượng tờ tiền trong V. w(n, V) chuyển thành W(n, V, m). Viết W(15, [10,5,2], 3) hiểu là w(15, [10,5,2]); W(15, [10,5,2], 2) hiểu là w(15, [10,5]). Quy ước thêm nữa V[1] là mệnh giá đầu tiên trong V, V[m] là mệnh giá cuối cùng.

    vậy ta có công thức đệ quy tổng quát: W(n, V, m) = W(n - V[m], V, m) + W(n, V, m-1)

    đệ quy thì phải có điều kiện dừng, hay base cases. Điều kiện dừng ở đây là
    - nếu n = 0, thì W(0, V, m) = 1
    - nếu n < 0, thì W(n, V, m) = 0
    - nếu n > 0 và m < 1, thì W(n, V, m) = 0

    code C++14:
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. using IntArray = std::vector<int>;
    5.  
    6. int W(int n, const IntArray& V, int m)
    7. {
    8.     if (n == 0) return 1;
    9.     if (n < 0 || m < 1) return 0;
    10.     return W(n - V[m-1], V, m) + W(n, V, m-1);
    11. }
    12.  
    13. int main()
    14. {
    15.     IntArray V{50,20,10,5,2};
    16.     std::cout << W(325, V, V.size()) << "\n";
    17.     std::cout << W(876, V, V.size()) << "\n";
    18.     std::cout << W(3, V, V.size()) << "\n";
    19. }

    cách này hơi chậm vì là đệ quy. Muốn nhanh hơn thì xài quy hoạch động, nói đơn giản là lưu lại các giá trị đã tính rồi để ko phải tính lại như đệ quy nữa.

    với quy hoạch động thì đi ngược lại từ nhỏ lên. Ở đây n tối đa là 1000 (10 triệu, mà là bội của 10 ngàn, nên chỉ có 1000 giá trị từ 1 tướng ứng với 10 ngàn tới 1000 tương ứng với 10 triệu), nên làm hẳn cái mảng 1000+1 phần tử luôn (thêm số 0), rồi đi từ nhỏ tới lớn. Kiểu na ná như Fibonacci ấy. Fibonacci đệ quy là F(n) = F(n-1) + F(n-2), thì thay vì đi từ F(1000) xuống F(999), F(998), F(997), v.v... thì ta có thể đi từ F(0) F(1) F(2) lên F(1000).

    ở đây khó hơn vì W(n, V, m) có tới 2 giá trị thay đổi là n và m. Cách giải là giữ nguyên 1 giá trị, ở đây là m, rồi tính W với n từ 0 tới 1000. Sau đó tăng m lên 1 đơn vị, rồi tính lại W từ 0 tới 1000, v.v... tới khi m = size(V).

    với m ko đổi, ta có W(n, V, m) = W(n, V, m) + W(n - V[m], V, m). Sở dĩ phải cộng dồn là vì m thay đổi, nên phần xanh lá thực chất chính là từ m cũ, hay là W(n, V, m-1).
    ví dụ n = 15, V = [10,5,2]. Ta tạo mảng p[0..15] gồm 16 phần tử, p[0] = 1 vì có đúng 1 cách thối 0 đồng:
         0  1  2  3  4  5  6  7   8  9 10 11 12 13 14 15
    m=0  1  0  0  0  0  0  0  0  0   0  0  0  0  0  0  0


    với m = 1, bắt đầu từ p[10] tới p[15], gán p[i] += p[i-10]
         0  1  2  3  4  5  6  7   8  9 10 11 12 13 14 15
    m=1  1  0  0  0  0  0  0  0  0   0  1  0  0  0  0  0


    với m = 2, bắt đầu từ p[5] tới p[15], gán p[i] += p[i-5]
         0  1  2  3  4  5  6  7   8  9 10 11 12 13 14 15
    m=2  1  0  0  0  0  1  0  0  0  0  2  0  0  0  0   2


    với m = 3, bắt đầu từ p[2] tới p[15], gán p[i] += p[i-2]
         0  1  2  3  4  5  6  7   8  9 10 11 12 13 14 15
    m=3  1  0  1  0  1  1  1  1  1  1  3  1   3  1  3  3


    code C++14:
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. using IntArray = std::vector<int>;
    5.  
    6. auto Wdp(int n, const IntArray& V)
    7. {
    8.     IntArray p(n+1, 0);
    9.     p[0] = 1;
    10.     for (int m = 0; m < V.size(); ++m)
    11.         for (int i = V[m]; i <= n; ++i)
    12.             p[i] += p[i-V[m]];
    13.     return p;
    14. }
    15.  
    16. int main()
    17. {
    18.     IntArray V{50,20,10,5,2};
    19.     auto p = Wdp(1000, V);
    20.     std::cout << p[325] << "\n";
    21.     std::cout << p[876] << "\n";
    22.     std::cout << p[3] << "\n";
    23. }

    code có 6-7 dòng mà giải thích thì dài dòng ~.~
    mà anh ơi mấy cái mảng trên lớp em chưa đc học tới @@ Với cái thư viện vector luôn á...

  4. #4
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Trích dẫn Nguyên bản được gửi bởi kkkbik Xem bài viết
    mà anh ơi mấy cái mảng trên lớp em chưa đc học tới @@ Với cái thư viện vector luôn á...
    N cỡ 10mil chắc chạy trâu được, nhưng còn phức tạp hơn =)

    Vầy là cách chuẩn rồi đấy.

  5. #5
    Ngày gia nhập
    05 2016
    Nơi ở
    Rạch giá
    Bài viết
    15

    Dù gì cũng cảm ơn mọi người đã vào chỉ. Và nhất là bác INTP... Em ko dám chép bậy bạ đâu ạ. Để tối nay đọc rồi nghiền ngẫm xem nó thấm đc tí nào ko :(( Chứ mới năm 1 vô mấy cái này gà mờ quá :(( Hic. Mới học xong vòng lập mà thầy đã cho bài như thế này :((

  6. #6
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Mặc định Bài toán về Quy Hoạch Động

    Mảng V có cần sắp xếp không nhỉ.

    Thực ra biến m trong công thức trên là "số mệnh giá" mới đúng. Công thức trên có thể hiểu là số cách đổi bằng cả V[1..m] sẽ bằng số cách đổi với m-1 m.g trước + số cách đổi sau khi đã trừ đi (1 tờ) mệnh giá V[m] (với cả m mệnh giá, nếu không sẽ bị sót). Độ phức tạp là O(số mệnh giá*số tiền).
    Đã được chỉnh sửa lần cuối bởi prog10 : 13-03-2017 lúc 02:09 AM.

  7. #7
    Ngày gia nhập
    07 2011
    Bài viết
    465

    năm 1 thì học cách sử dụng ngôn ngữ mà vọc mấy bài qhđ làm gì @_@ Mấy bài kiểu này giải tay rồi áp dụng vô code chứ đâu phải học code.

    @prog10 có lẽ ko cần sắp xếp đâu. Mà số lượng mệnh giá tiền đúng hơn chứ số lượng tờ tiền dễ gây hiểu lầm

  8. #8
    Ngày gia nhập
    05 2016
    Nơi ở
    Rạch giá
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi INTP Xem bài viết
    năm 1 thì học cách sử dụng ngôn ngữ mà vọc mấy bài qhđ làm gì @_@ Mấy bài kiểu này giải tay rồi áp dụng vô code chứ đâu phải học code.

    @prog10 có lẽ ko cần sắp xếp đâu. Mà số lượng mệnh giá tiền đúng hơn chứ số lượng tờ tiền dễ gây hiểu lầm
    Mà vấn đề ở đây như em nói đó a.
    Em làm cái số a 5 dòng for là nó muốn đơ luôn rồi...
    Còn đề hỏi số b là số lượng tờ tiền ít nhất mà atm có thể đưa ra... <---- Ko hiểu cái này lắm

  9. #9
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Trích dẫn Nguyên bản được gửi bởi kkkbik Xem bài viết
    Mà vấn đề ở đây như em nói đó a.
    Em làm cái số a 5 dòng for là nó muốn đơ luôn rồi...
    Còn đề hỏi số b là số lượng tờ tiền ít nhất mà atm có thể đưa ra... <---- Ko hiểu cái này lắm
    Cách suy nghĩ để giải thì nãy giờ @INTP đã trình bày rồi. Câu b/ làm tương tự thôi. (Đồng ý là rất khó với bạn nhưng mà cách này đã có làm mẫu rồi)

    Với 1-2-5 thì chia xuống trừ ra là được.
    Đã được chỉnh sửa lần cuối bởi prog10 : 20-09-2017 lúc 10:58 AM.

  10. #10
    Ngày gia nhập
    05 2016
    Nơi ở
    Rạch giá
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi prog10 Xem bài viết
    Cách suy nghĩ để giải thì nãy giờ @INTP đã trình bày rồi. Câu b/ làm tương tự thôi. (Đồng ý là rất khó với bạn nhưng mà cách này đã có làm mẫu rồi)

    Mình đã từng nói là với 1-2-5 thì chia xuống trừ ra là được.
    Mà cảm ơn mod và anh INTP nhiều lắm ạ. Chắc phải nghiền ngẫm nhiều nữa mới hiểu nổi ^^

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn