Thuật toán lập trình động N, K problem

Question

Thuật toán sẽ lấy hai số dương N và K và tính số lượng lớn nhất có thể bằng cách chuyển N thành số khác bằng cách xóa số K khỏi N.

Ví dụ: giả sử chúng ta có N = 12345 và K = 3 nên số lượng lớn nhất có thể có được bằng cách loại bỏ 3 chữ số từ N là 45 (các biến đổi khác là 12, 15, 35 nhưng 45 là lớn nhất). Ngoài ra, bạn không thể thay đổi thứ tự của các chữ số trong N (vì vậy 54 KHÔNG phải là một giải pháp). Một ví dụ khác là N = 66621542 và K = 3 để giải pháp sẽ là 66654.

Tôi biết đây là vấn đề liên quan đến lập trình động và tôi không thể có bất kỳ ý tưởng nào về cách giải quyết nó. Tôi cần phải giải quyết điều này trong 2 ngày, vì vậy bất kỳ trợ giúp được đánh giá cao. Nếu bạn không muốn giải quyết điều này cho tôi, bạn không cần phải làm gì, nhưng hãy chỉ cho tôi mẹo hoặc ít nhất một số tài liệu mà tôi có thể đọc thêm về một số vấn đề tương tự.

Cảm ơn bạn trước.

Answer 1

Bí quyết giải quyết vấn đề lập trình động thường là để tìm ra cấu trúc của giải pháp trông như thế nào và cụ thể hơn nếu nó thể hiện cấu trúc con tối ưu tối ưu.

Trong trường hợp này, có vẻ như với tôi rằng giải pháp tối ưu với N = 12345 và K = 3 sẽ có một giải pháp tối ưu cho N = 12345 và K = 2 như là một phần của giải pháp. Nếu bạn có thể thuyết phục bản thân rằng điều này giữ, sau đó bạn sẽ có thể thể hiện một giải pháp cho vấn đề đệ quy. Sau đó, hoặc thực hiện điều này với memoisation hoặc từ dưới lên.

Answer 2

Đây là những gì tôi nghĩ:

Xem xét k + 1 chữ số đầu tiên từ bên trái. Hãy tìm cái lớn nhất, tìm nó và loại bỏ các con số ở bên trái. Nếu có hai số lớn nhất, hãy tìm số còn lại lớn nhất và xóa số ở bên trái số đó. lưu trữ số chữ số đã xóa (tên nó là j).

Làm điều tương tự với số mới là N và k + 1-j khi K. Thực hiện việc này cho đến khi k + 1 -j bằng 1 (hy vọng, nó sẽ, nếu tôi không nhầm).

Số bạn kết thúc sẽ là số bạn đang tìm kiếm.

Answer 3

Hai yếu tố quan trọng nhất của bất kỳ giải pháp quy hoạch động là:

1. Xác định quyền bài toán
2. Xác định một mối quan hệ tái phát giữa câu trả lời cho một tiểu vấn đề và câu trả lời cho nhỏ các vấn đề phụ
3. Tìm kiếm trường hợp cơ sở, các vấn đề phụ nhỏ nhất có câu trả lời không phụ thuộc vào bất kỳ câu trả lời nào khác
4. Tìm ra các quét để trong đó bạn phải giải quyết bài toán (để bạn bao giờ sử dụng các mối quan hệ tái phát dựa trên dữ liệu chưa được khởi tạo)

Bạn sẽ biết rằng bạn có bài toán đúng được xác định khi

• vấn đề bạn cần câu trả lời cho là một trong số họ
• các trường hợp cơ sở thực sự là tầm thường
• việc lặp lại dễ dàng đánh giá
• Trình tự quét là đơn giản

Trong trường hợp của bạn, nó là đơn giản để xác định bài toán. Vì đây có lẽ là bài tập về nhà, tôi sẽ chỉ cung cấp cho bạn gợi ý rằng bạn có thể muốn rằng N có ít chữ số hơn để bắt đầu với.

Answer 4

Vâng, để giải quyết bất kỳ vấn đề lập trình động nào, bạn cần phải chia nhỏ nó thành các phần tử định kỳ.

Giả sử chúng tôi xác định vấn đề của bạn là A (n, k), trả về số lớn nhất có thể bằng cách xóa k chữ số khỏi n.

Chúng tôi có thể xác định một thuật toán đệ quy đơn giản từ điều này.

Sử dụng ví dụ của bạn, A (12345, 3) = max {A (2345, 2), A (1345, 2), A (1245, 2), A (1234, 2)}

More nói chung, A (n, k) = tối đa {A (n với 1 chữ số được xóa, k - 1)}

Và trường hợp cơ sở của bạn là A (n, 0) = n.

Sử dụng phương pháp này, bạn có thể tạo bảng lưu trữ giá trị của n và k.

int A(int n, int k) 
{ 
    typedef std::pair<int, int> input; 
    static std::map<input, int> cache; 

    if (k == 0) return n; 

    input i(n, k); 
    if (cache.find(i) != cache.end()) 
    return cache[i]; 

    cache[i] = /* ... as above ... */ 

    return cache[i]; 
} 

Bây giờ, đó là giải pháp chuyển tiếp thẳng, nhưng có giải pháp tốt hơn hoạt động với bộ nhớ cache một chiều rất nhỏ. Hãy xem xét rephrasing câu hỏi như thế này: "Cho một chuỗi n và số nguyên k, tìm các bước lexicographically lớn nhất trong n của chiều dài k". Đây chính là vấn đề của bạn, và giải pháp đơn giản hơn rất nhiều.

Bây giờ chúng ta có thể định nghĩa một khác nhau chức năng B (i, j), mang đến cho các chuỗi hoặc null lớn nhất có chiều dài (i - j), chỉ sử dụng i chữ số đầu tiên của n (trong các từ khác, đã xóa j chữ số từ i chữ số đầu tiên của n).

Sử dụng ví dụ của bạn một lần nữa, chúng ta sẽ có:

B (1, 0) = 1

B (2, 0) = 12

B (3, 0) = 123

B (3, 1) = 23

B (3, 2) = 3

, vv

Với một chút suy nghĩ, chúng ta có thể tìm ra mối quan hệ tái phát:

B (i, j) = max (10B (i-1, j) + n _i, B (i-1, j-1))

hoặc, nếu j = i sau đó B (i, j) = B (i-1, j-1)

và B (0, 0) = 0

Và bạn có thể mã hóa đó lên một cách rất tương tự như trên.

Answer 5

Điều này có thể được giải quyết bằng O (L) trong đó L = số chữ số. Tại sao sử dụng các công thức DP phức tạp khi chúng ta có thể sử dụng ngăn xếp để thực hiện việc này:

Cho: 66621542 Thêm chữ số vào ngăn xếp có ít hơn hoặc bằng chữ số L - K trên ngăn xếp: 66621. Bây giờ, xóa chữ số khỏi ngăn xếp trong khi chúng nhỏ hơn chữ số hiện đang đọc và đặt chữ số hiện tại trên ngăn xếp:

đọc 5: 5> 2, pop 1 khỏi ngăn xếp. 5> 2, pop 2 cũng vậy. đặt 5: 6665 đọc 4: ngăn xếp không đầy, đặt 4: 66654 đọc 2: 2 < 4, không làm gì cả.

Bạn cần thêm một điều kiện: đảm bảo không bật thêm các mục từ ngăn xếp so với số còn lại trong số của bạn, nếu không giải pháp của bạn sẽ không đầy đủ!

Một ví dụ khác: 12345 L = 5, K = 3 đặt L - K = 2 chữ số trên stack: 12

đọc 3, 3> 2, pop 2, 3> 1, pop 1, đặt 3.ngăn xếp: 3 đọc 4, 4> 3, pop 3, đặt 4: 4 đọc 5: 5> 4, nhưng chúng tôi không thể bật 4, nếu không chúng tôi sẽ không còn đủ chữ số. vì vậy hãy đẩy 5: 45.