मान लीजिए हमारे पास पत्थरों का एक संग्रह है, जहां प्रत्येक पत्थर का एक धनात्मक पूर्णांक वजन है। प्रत्येक चरण में, हम किन्हीं दो पत्थरों को चुनकर उन्हें आपस में टकराते हैं। यदि पत्थरों के वजन x और y हैं जहां x ≤ y, तो इस टकराव का परिणाम निम्न होगा:
यदि x = y, तो दोनों पत्थर पूरी तरह नष्ट हो जाते हैं;
यदि x ≠ y, तो वजन x वाला पत्थर पूरी तरह नष्ट हो जाता है, और वजन y वाले पत्थर का नया वजन y-x हो जाता है।
अंत में, अधिकतम 1 पत्थर बचता है। हमें इस बचे हुए पत्थर के सबसे छोटे संभावित वजन को खोजना है (यदि कोई पत्थर नहीं बचता तो वजन 0 होगा)।
उदाहरण के लिए, यदि इनपुट [2,7,4,1,8,1] है, तो आउटपुट 1 होगा। ऐसा इसलिए क्योंकि यदि हम (2,4) को टकराते हैं, तो नया ऐरे [2,7,1,8,1] बनेगा, फिर (7,8) को टकराने पर [2,1,1,1], फिर (2,1) पर [1,1,1], और अंत में (1,1) टकराने पर केवल 1 बचेगा।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्न चरणों का पालन करेंगे:
n := पत्थरों के ऐरे का आकार, total := 0 सेट करें
i को 0 से n-1 तक लूप में total में stones[i] जोड़ें
req := total / 2 की गणना करें
आकार req+1 का एक dp ऐरे बनाएं और इसे false से भरें
dp[0] := true, reach := 0 सेट करें
प्रत्येक पत्थर के लिए, j को req से stones[i] तक घटाते हुए dp[j] को अपडेट करें और reach को ट्रैक करें
अंत में total - (2 * reach) लौटाएं
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size();
int total = 0;
for(int i = 0; i < n; i++){
total += stones[i];
}
int req = total / 2;
vector<bool> dp(req + 1, false);
dp[0] = true;
int reach = 0;
for(int i = 0; i < n; i++){
for(int j = req; j - stones[i] >= 0; j--){
dp[j] = dp[j] || dp[j - stones[i]];
if(dp[j]) reach = max(reach, j);
}
}
return total - (2 * reach);
}
};
int main(){
vector<int> v = {2,7,4,1,8,1};
Solution ob;
cout << (ob.lastStoneWeightII(v));
return 0;
}
इनपुट
[2,7,4,1,8,1]
आउटपुट
1
