資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在C++中查詢房屋中可能被盜的最大價值
在這個問題中，我們得到了n棟房子，其中包含一些價值。我們的任務是找到房屋中可能被盜的最大價值。
問題描述 − 我們有一個數組houses[]，它包含每個房子中的值。一個小偷搶劫了這些房子，但他不能從兩個相鄰的房子偷東西，因為鄰居知道盜竊事件。我們需要找到小偷從房子裡偷到的最大可能價值，而不會被抓住。
讓我們舉個例子來理解這個問題，
輸入
houses[] = {5, 2, 1, 6, 7, 9, 4, 3}輸出
23
解釋
The max values can be stolen as : 5, 6, 9, 3.
解決方案方法
可以使用動態規劃找到問題的解決方案。因為我們需要找到小偷盜竊的最大價值，這樣如果他從索引i處的房子偷竊，那麼他不能從索引(i+1)處的房子偷竊。此外，我們不會從索引(i-1)處的房子偷竊。為了解決這個問題，我們將建立一個大小為n的DP陣列。對於基本情況，我們將DP[0]初始化為houses[0]，並將DP[1]初始化為houses[1]。然後，我們將找到從索引2到n-1的所有DP值。DP[i]的值將是DP[i-2] + houses[i]或DP[i-1]中的最大值。最後，DP陣列的最後一個值是可以盜竊的最大值。
程式說明我們解決方案的工作原理，
示例
#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;
}輸出
The maximum possible values stolen from the houses is 23
此解決方案很好，但可以使用以下事實使其效率更高：可以使用僅兩個值找到被盜的最大值。因為在DP中，我們對每個索引只使用了兩個值。因此，我們可以僅使用兩個變數來找到解決方案，這將空間複雜度降低到問題，
程式說明我們解決方案的工作原理，
示例
#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;
}輸出
The maximum possible values stolen from the houses is 23
更新於： 2021年3月12日
570 次瀏覽
廣告