Stolen Values Problem using Dynamic Programming

«
»

This is a C++ Program that Solves Stolen Values Problem using Dynamic Programming technique.

Problem Description

There are n houses built in a line, each of which contain some value in it. A thief is going to steal in these houses. But he cannot steal in two adjacent houses. What is maximum value he can steal?

Problem Solution

Maximum stolen value from first i houses of the line can be either the maximum stolen value from first i-1 houses of the line or maximum stolen value from i-2 houses of the line plus value in ith house. So, we will choose maximum of these. We will calculate the values in bottom up manner.

Expected Input and Output

Case-1:

 
number of houses=7
values[]=9, 3, 5, 8, 2, 4, 7
maximum stolen value=24 by stealing from first, fourth and seventh house
Program/Source Code

Here is source code of the C++ Program to Solve Stolen Values Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. int maxStolen(int n, int values[])
  6. {
  7.     //array to store results
  8.     int dp[n+1];
  9.  
  10.     //dp[i]=maximum stolen value from first i houses
  11.  
  12.     dp[0]=0;
  13.     dp[1]=values[1];
  14.  
  15.     for(int i=2;i<=n;i++)
  16.     {
  17.         //maximum stolen value from first i houses of the line can be 
  18.         //either the maximum stolen value from first i-1 houses of the line
  19.         //or maximum stolen value from i-2 houses of the line plus value in ith house
  20.         //so, we will choose maximum of these
  21.         dp[i]=max(dp[i-1],dp[i-2]+values[i]);
  22.     }
  23.  
  24.     return dp[n];
  25. }
  26.  
  27.  
  28. int main()
  29. {
  30.     int n;
  31.     cout<<"Enter the number of houses"<<endl;
  32.     cin>>n;
  33.  
  34.     int values[n+1];
  35.     cout<<"Enter the values in the houses"<<endl;
  36.     for(int i=1;i<=n;i++)
  37.         cin>>values[i];
  38.  
  39.     cout<<"Maximum stolen value is "<<endl;
  40.     cout<<maxStolen(n, values);
  41.  
  42.     cout<<endl;
  43.     return 0;
  44. }
Program Explanation

In the main function, we ask the user to input the value of number of houses and values in each house to be stolen. We pass these values to the function maxStolen as parameters. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases
 
Case-1:
$ g++ stolen_values.cpp
$ ./a.out
Enter the number of houses
7
Enter the values in the houses
9 3 5 8 2 4 7
Maximum stolen value is 
24

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.