ในปัญหานี้ เราได้รับบ้าน 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) เพื่อแก้ปัญหา เราจะสร้างอาร์เรย์ DP ขนาด n และสำหรับกรณีพื้นฐาน เราจะเริ่มต้น DP[0] ด้วย house[0] และ DP[1] ด้วย house[1] จากนั้น เราจะหาค่าทั้งหมดของ DP จากดัชนี 2 ถึง n-1 ค่าของDP[i]จะเป็นค่าสูงสุดจาก DP[i-2] + house[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 เราใช้เพียงสองค่าสำหรับแต่ละดัชนี ดังนั้น เราจึงใช้ตัวแปรได้เพียง 2 ตัวในการค้นหาวิธีแก้ปัญหาคือลดความซับซ้อนของพื้นที่ลง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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
