Cho một mảng số nguyên chia mảng thành 2 tập con JavaScript
|
Cho một tập hợp các số nguyên dương Show Ví dụ, hãy xem xét ________số 8_______ Lưu ý rằng giải pháp này không phải là duy nhất. Sau đây là một giải pháp khác
Vấn đề này là một phiên bản tối ưu hóa của vấn đề phân vùng. Ý tưởng là xem xét từng mục trong tập hợp đã cho
Cuối cùng, trả về chênh lệch tối thiểu mà chúng tôi nhận được bằng cách bao gồm mục hiện tại trong C++1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #include #include sử dụng không gian tên std;
// Phân vùng đặt `S` thành hai tập con, `S1` và `S2`, sao cho // chênh lệch giữa tổng các phần tử trong `S1` và tổng // các phần tử trong `S2` được thu nhỏ int findMinAbsDiff(vectơ<int> const &S, int n, int S1, int S2) { // Trường hợp cơ bản. nếu danh sách trống, hãy trả về giá trị tuyệt đối // chênh lệch giữa cả hai nhóm nếu (n < 0) { trả lại abs(S1 - S2); }
// Trường hợp 1. Bao gồm mục hiện tại trong tập hợp con `S1` và lặp lại // cho các mục còn lại `n-1` int inc = findMinAbsDiff(S, n - 1, S1 + S[n], S2);
// Trường hợp 2. Loại trừ mục hiện tại khỏi tập hợp con `S1` và lặp lại cho // các mục còn lại `n-1` int exc = findMinAbsDiff(S, n - 1, S1, S2 + S[n]);
trả lại phút(inc, exc); }
int chính() { // Đầu vào. một tập hợp các mục vectơ<int> S = { 10, 20, 15, 5, 25};
// tổng số mục int n = S.kích thước();
cout << "Chênh lệch tối thiểu là " << findMinAbsDiff(S, n - 1, 0, 0);
return 0; } Tải xuống Chạy mã đầu ra Java1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 lớp Chính { // Phân vùng đặt `S` thành hai tập con, `S1` và `S2`, sao cho // chênh lệch giữa tổng các phần tử trong `S1` và tổng // các phần tử trong `S2` được thu nhỏ công khai tĩnh int findMinAbsDiff(int[] S, int n, int S1, int S2) { // Trường hợp cơ bản. nếu danh sách trống, hãy trả về giá trị tuyệt đối // chênh lệch giữa cả hai nhóm nếu (n < 0) { return Toán. abs(S1 - S2); }
// Trường hợp 1. Bao gồm mục hiện tại trong tập hợp con `S1` và lặp lại // cho các mục còn lại `n-1` int inc = findMinAbsDiff(S, n - 1, S1 + S[n], S2);
// Trường hợp 2. Loại trừ mục hiện tại khỏi tập hợp con `S1` và lặp lại cho // các mục còn lại `n-1` int exc = findMinAbsDiff(S, n - 1, S1, S2 + S[n]);
trả về Số nguyên. phút(inc, exc); }
công khai tĩnh vô hiệu chính(String[] args) { // Đầu vào. một tập hợp các mục int[] S = { 10, 20, 15, 5, 25 };
Hệ thống. ra. println("Sự khác biệt tối thiểu là " + findMinAbsDiff(S, S.độ dài - 1, 0, 0)); } } Tải xuống Chạy mã đầu ra con trăn1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 # Phân vùng đặt `S` thành hai tập con, `S1` và `S2`, sao cho # chênh lệch giữa tổng các phần tử trong `S1` và tổng # phần tử trong `S2` được thu nhỏ def findMinAbsDiff(S, n, S1=0, S2=0):
# Trường hợp cơ bản. nếu danh sách trống, hãy trả về giá trị tuyệt đối # chênh lệch giữa cả hai nhóm nếu n < 0: trả lại abs(S1 - S2)
# Trường hợp 1. Bao gồm mục hiện tại trong tập hợp con `S1` và lặp lại # cho các mục còn lại `n-1` inc = findMinAbsDiff(S, n - 1, S1 + S[n], S2)
# Trường hợp 2. Loại trừ mục hiện tại khỏi tập hợp con `S1` và lặp lại cho # mục còn lại `n-1` exc = findMinAbsDiff(S, n - 1, S1, S2 + S[n])
trả lại phút(inc, exc)
if __name__ == '__main__'.
# Đầu vào. một tập hợp các mục S = [10, 20, 15, 5, 25]
in('Chênh lệch tối thiểu là', findMinAbsDiff(S, len(S) - 1))
Tải xuống Chạy mã đầu ra Độ phức tạp về thời gian của giải pháp trên là theo cấp số nhân và chiếm không gian trong ngăn xếp cuộc gọi Chúng tôi biết rằng các vấn đề với cấu trúc con tối ưu và các bài toán con chồng chéo có thể được giải quyết bằng quy hoạch động, trong đó các giải pháp của bài toán con được ghi nhớ thay vì tính toán lặp đi lặp lại Sau đây là phiên bản ghi nhớ trong C++, Java và Python tuân theo cách tiếp cận từ trên xuống vì trước tiên chúng tôi chia vấn đề thành các bài toán con, sau đó tính toán và lưu trữ các giá trị |
