Trong bài toán này, chúng ta được đưa ra n ngôi nhà với một số giá trị trong đó. Nhiệm vụ của chúng tôi là Tìm giá trị tối đa có thể bị đánh cắp từ các ngôi nhà.
Mô tả sự cố - Chúng tôi có một dãy nhà [] bao gồm các giá trị có trong mỗi ngôi nhà. Một tên trộm cướp nhà nhưng anh ta không thể ăn trộm từ hai ngôi nhà liền kề như những người hàng xóm biết về vụ trộm. Chúng ta cần tìm ra giá trị lớn nhất có thể mà kẻ trộm có thể lấy được từ ngôi nhà mà không bị bắt.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
houses[] = {5, 2, 1, 6, 7, 9, 4, 3} Đầu ra
23
Giải thích
The max values can be stolen as : 5, 6, 9, 3.
Phương pháp tiếp cận giải pháp
Giải pháp của vấn đề có thể được tìm thấy bằng cách sử dụng lập trình động. Vì chúng ta cần tìm giá trị bị trộm tối đa của kẻ trộm sao cho nếu hắn ăn trộm từ một ngôi nhà ở chỉ số i, thì anh ta không thể ăn trộm từ ngôi nhà ở chỉ mục (i + 1). Ngoài ra, chúng tôi sẽ không bị trộm từ ngôi nhà ở chỉ mục (i-1). Để giải quyết vấn đề, chúng ta sẽ tạo một mảng DP có kích thước n. Và đối với trường hợp cơ sở, chúng ta sẽ khởi tạo DP [0] với nhà [0] và DP [1] với nhà [1]. Sau đó, chúng ta sẽ tìm tất cả các giá trị của DP từ chỉ số 2 đến n-1. Giá trị củaDP [i] sẽ là giá trị lớn nhất trong số DP [i-2] + nhà [i] hoặc DP [i-1]. Và ở cuối giá trị cuối cùng của mảng DP là giá trị lớn nhất có thể bị đánh cắp.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
int calMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxValuesStolen(int houses[], int n) {
if (n == 0)
return 0;
int DP[n];
DP[0] = houses[0];
DP[1] = calMax(houses[0], houses[1]);
for (int i = 2; i<n; i++)
DP[i] = calMax( (houses[i] + DP[i-2]), DP[i-1]);
return DP[n-1];
}
int main() {
int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
int n = sizeof(houses)/sizeof(houses[0]);
cout<<"The maximum possible values stolen from the houses is
"<<findMaxValuesStolen(houses, n);
return 0;
} Đầu ra
The maximum possible values stolen from the houses is 23
Giải pháp này là tốt nhưng nó có thể được thực hiện hiệu quả hơn bằng cách sử dụng thực tế là các giá trị tối đa bị đánh cắp có thể được tìm thấy chỉ bằng cách sử dụng hai giá trị. Như trong DP, chúng tôi chỉ sử dụng hai giá trị cho mỗi chỉ mục. Vì vậy, chúng ta chỉ có thể sử dụng hai biến để tìm giải pháp làm giảm độ phức tạp của không gian cho vấn đề,
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
int calMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxValuesStolen(int houses[], int n) {
if (n == 0)
return 0;
int maxValStolen;
int val1 = houses[0];
int val2 = calMax(houses[0], houses[1]);
for (int i = 2; i<n; i++) {
maxValStolen = calMax( (houses[i]+val1) , val2);
val1 = val2;
val2 = maxValStolen;
}
return maxValStolen;
}
int main() {
int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
int n = sizeof(houses)/sizeof(houses[0]);
cout<<"The maximum possible values stolen from the houses is "<<findMaxValuesStolen(houses, n);
return 0;
} Đầu ra
The maximum possible values stolen from the houses is 23