এই সমস্যায়, আমাদের কিছু মান সহ n ঘর দেওয়া হয়। আমাদের কাজ হল বাড়ি থেকে চুরি হওয়া সর্বাধিক সম্ভাব্য মূল্য খুঁজে বের করা।
সমস্যা বর্ণনা − আমাদের একটি অ্যারে হাউস রয়েছে[] যা প্রতিটি বাড়িতে থাকা মানগুলি নিয়ে গঠিত। একজন চোর বাড়িতে ডাকাতি করে কিন্তু প্রতিবেশীরা চুরির কথা জানে বলে সে পাশের দুটি বাড়ি থেকে চুরি করতে পারে না। আমাদের সর্বাধিক সম্ভাব্য মূল্য খুঁজে বের করতে হবে যা চোর ধরা না পড়ে বাড়ি থেকে চুরি করতে পারে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
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]-কে হাউস[0] দিয়ে শুরু করব এবং DP[1] ঘরগুলি[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
এই সমাধানটি ভাল কিন্তু শুধুমাত্র দুটি মান ব্যবহার করে চুরি হওয়া সর্বাধিক মানগুলি খুঁজে পাওয়া যায় এই সত্যটি ব্যবহার করে এটি আরও দক্ষ করা যেতে পারে। ডিপির মতো, আমরা প্রতিটি সূচকের জন্য মাত্র দুটি মান ব্যবহার করেছি। সুতরাং, আমরা সমাধান খুঁজে পেতে শুধুমাত্র দুটি পরিবর্তনশীল ব্যবহার করতে পারি যা সমস্যার স্থান জটিলতা হ্রাস করে,
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
