Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Bài toán maximum sum plateau

  1. #1
    Ngày gia nhập
    08 2011
    Bài viết
    17

    Question Bài toán maximum sum plateau

    Đề bài: Cho 1 ma trận kích thước m x n gồm các phần tử gồm âm và dương. Viết chương trình tìm ma trận con của ma trận đã cho sao cho tổng của các phần tử trong ma trận con là lớn nhất có thể.

    Bài tìm mảng con 1 chiều có tổng lớn nhất có thể thì mình làm được rồi chứ bài này nghĩ nát óc mà vẫn không nghĩ ra. Vậy mong mọi người giúp đỡ. Thanks 4 reading!
    Code:
    Sờ tu pít :(

  2. #2
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Trích dẫn Nguyên bản được gửi bởi Pop Xem bài viết
    Đề bài: Cho 1 ma trận kích thước m x n gồm các phần tử gồm âm và dương. Viết chương trình tìm ma trận con của ma trận đã cho sao cho tổng của các phần tử trong ma trận con là lớn nhất có thể.

    Bài tìm mảng con 1 chiều có tổng lớn nhất có thể thì mình làm được rồi chứ bài này nghĩ nát óc mà vẫn không nghĩ ra. Vậy mong mọi người giúp đỡ. Thanks 4 reading!
    - Ma trận bất kì luôn có kích thước mxn: Do đó số phần tử ko thể là số nguyên tố
    - Tổng lớn nhất có thể -> Tổng các số dương. Kiểm tra xem số phần tử dương có là số nguyên tố ko. Nếu là số nguyên tố thì ta loại bỏ phần tử dương nhỏ nhất
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

  3. #3
    Ngày gia nhập
    08 2011
    Bài viết
    17

    Trích dẫn Nguyên bản được gửi bởi beautifulsoul84hung Xem bài viết
    - Ma trận bất kì luôn có kích thước mxn: Do đó số phần tử ko thể là số nguyên tố
    - Tổng lớn nhất có thể -> Tổng các số dương. Kiểm tra xem số phần tử dương có là số nguyên tố ko. Nếu là số nguyên tố thì ta loại bỏ phần tử dương nhỏ nhất
    Có lẽ bạn đã hiểu sai yêu cầu bài toán rồi. Không biết bạn đã đọc bài này chưa:

    Có thể một loạt các số(gồm cả số âm nhưng trong cái ma trận con đó lại chứa những số dương lớn hơn rất nhiều so với số âm và những số dương còn lại trong ma trận ban đầu) thì tổng đó vẫn là lớn nhất dù vẫn chứa phần tử âm. Có những ma trận con chỉ toàn phần tử dương nhưng mà nhỏ quá thì tổng của chúng cũng chẳng đáng bao nhiêu
    Code:
    Sờ tu pít :(

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

    Mình cũng chẳng nghĩ ra cách nào giải bài này ngoài cứ for 4 vòng ( O(m*m*n*n) )
    Thử chạy với m = n = 100 thì vẫn ra kết quả ngay.

    C++ Code:
    1. #include <iostream>
    2. #include <cstdio>
    3. #include <cstdlib>
    4.  
    5. enum {MAXN = 100};
    6. long a[MAXN + 1][MAXN + 1];
    7. long h[MAXN + 1][MAXN + 1], hc[MAXN + 1][MAXN + 1];  // nếu dữ liệu lớn thì khai báo double
    8. // Chú ý: Trong bài này các chỉ số của ma trận được tính từ [1][1] đến [m][n]
    9. struct Rect {
    10.     int m1, n1, m2, n2;
    11. };
    12.  
    13. int main()
    14. {
    15.     int m = 4, n = 4;
    16.     for (int i = 1; i <= m; ++i) {
    17.         for (int j = 1; j <= n; ++j) {
    18.             a[i][j] = rand() % 1000 - 500;
    19.         }
    20.     }
    21.  
    22.     //  Ti'nh h[i][j] = a[i][1] + a[i][2] + ... + a[i][j]
    23.     for (int i = 1; i <= m; ++i) {
    24.         h[i][0] = 0;
    25.         for (int j = 1; j <= n; ++j)
    26.             h[i][j] = h[i][j - 1] + a[i][j];
    27.     }
    28.  
    29.     //  Ti'nh hc[i][j] = tong cac so trong ma tran con tu [1][1] den [i][j]
    30.     for (int i = 0; i <= m; ++i) hc[i][0] = 0;
    31.     for (int j = 1; j <= n; ++j) {
    32.         hc[0][j] = 0;
    33.         for (int i = 1; i <= m; ++i)
    34.             hc[i][j] = hc[i - 1][j] + h[i][j];
    35.     }
    36.  
    37.     Rect r, maxr;
    38.     long max_sum = -2e9;
    39.     for (r.m1 = 1; r.m1 <= m; ++r.m1) {
    40.         for (r.n1 = 1; r.n1 <= n; ++r.n1) {
    41.             for (r.m2 = r.m1; r.m2 <= m; ++r.m2) {
    42.                 for (r.n2 = r.n1; r.n2 <= n; ++r.n2) {
    43.                     long sum = hc[r.m2][r.n2] - hc[r.m1 - 1][r.n2] - hc[r.m2][r.n1 - 1] + hc[r.m1 - 1][r.n1 - 1];
    44.                     if (sum < max_sum) continue;
    45.                     max_sum = sum;
    46.                     maxr = r;
    47.                 }
    48.             }
    49.         }
    50.     }
    51.  
    52.     printf("max_sum = %ld, a[%d..%d, %d..%d]", max_sum, maxr.m1, maxr.m2, maxr.n1, maxr.n2);
    53. }

    Nếu tối ưu code thì có thể làm nó chạy nhanh khoảng gấp 2, nhưng sẽ khó nhìn khó hiểu hơn. Có lẽ chẳng cần.
    Đã được chỉnh sửa lần cuối bởi fbchicken : 09-09-2011 lúc 04:26 PM. Lý do: Đổi chỉ số ma trận tính từ [1][1] thay vì [0][0]. Ngoài ra code cũ sai sót thiếu 1 vài trường hợp

  5. #5
    Ngày gia nhập
    01 2010
    Nơi ở
    Hà Nội
    Bài viết
    128

    Bài này và bài tìm trong mảng 1 chiều là như nhau .
    Bằng cách đổ mảng 2 chiều sang mảng 1 chiều để tìm.
    Sau đó đổ ngược lại và in
    Còn cách đổ mảng 1->2 và ngược lại thì bạn tìm trong 4rum đã có .
    Thân !

  6. #6
    Ngày gia nhập
    08 2011
    Bài viết
    17

    Mặc định Bài toán maximum sum plateau

    Cám ơn mọi người đã giúp đỡ. Nhưng mà code của fb thì mình cần chút thời gian để hiểu. Thực sự thì trong suy nghĩ của mình về bài này rất phức tạp và không thể tìm cách gỡ rồi được. Vậy ai đó chỉ giùm mình thuật toán giải quyết bài này được không?
    Code:
    Sờ tu pít :(

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

    Code của mình thì for 4 vòng,tính tổng từng ma trận con thôi chứ có gì khó hiểu đâu. Chi phí tính tổng mỗi ma trận con khá bé nên chạy m = n = 100 vẫn < 1s. Nếu đề bài cho 1 <= m,n <= 100 thì cách đó cũng đủ. Còn suy nghĩ theo hướng tìm thuật toán đỉnh cao thì mình cũng thấy phức tạp thật.

Các đề tài tương tự

  1. ADO.NET Lỗi " Some text formatting may have changed in this file because the maximum number of fonts was exceeded"..
    Gửi bởi teodainhan trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 0
    Bài viết cuối: 30-12-2013, 07:16 PM

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