数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告