समस्या विवरण
मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, अब दो सेट्स ढूंढें जिनके योग समान और अधिकतम हों, फिर योग मान ढूंढें।
उदाहरण के लिए, यदि इनपुट है nums = [2, 5, 4, 6], तो आउटपुट 6 होगा, क्योंकि सेट्स [2, 4] और [6] हैं।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- sum := 0
- nums में प्रत्येक संख्या i के लिए: sum := sum + i
- n := nums का आकार
- आकार (n+1) × (2*sum+5) का एक 2D ऐरे dp परिभाषित करें और -1 से भरें
- dp[0][sum] := 0
- i := 1 से n तक:
- x := nums[i-1]
- j := 0 से 2*sum+4 तक:
- यदि j-x >= 0 और dp[i-1][j-x] != -1, तो dp[i][j] := max(dp[i][j], dp[i-1][j-x] + x)
- यदि j+x < 2*sum+5 और dp[i-1][j+x] != -1, तो dp[i][j] := max(dp[i][j], dp[i-1][j+x])
- dp[i][j] := max(dp[i][j], dp[i-1][j])
- dp[n][sum] वापस करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int>& nums) {
int sum = 0;
for (int i : nums) sum += i;
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 5, -1));
dp[0][sum] = 0;
for (int i = 1; i <= n; i++) {
int x = nums[i - 1];
for (int j = 0; j < 2 * sum + 5; j++) {
if (j - x >= 0 && dp[i - 1][j - x] != -1) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - x] + x);
}
if (j + x < 2 * sum + 5 && dp[i - 1][j + x] != -1) {
dp[i][j] = max(dp[i][j], dp[i - 1][j + x]);
}
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
}
return dp[n][sum];
}
};
int solve(vector<int>& nums) {
return (new Solution())->solve(nums);
}
int main() {
vector<int> v = {2, 5, 4, 6};
cout << solve(v);
}
इनपुट
{2, 5, 4, 6}
आउटपुट
6
