資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢和相等的兩組數的最大和
假設我們有一個名為nums的數字列表，現在找到兩個和相等且最大的集合，然後找到和的值。
因此，如果輸入類似於nums = [2, 5, 4, 6]，則輸出將為6，因為集合為[2, 4]和[6]。
為了解決這個問題，我們將遵循以下步驟：
- sum := 0
- 對於nums中的每個數字i，執行以下操作：
- sum := sum + i
- n := nums的大小
- 定義一個大小為(n + 1) x (2 * sum + 5)的二維陣列dp，並用-1填充
- dp[0, sum] := 0
- 初始化i := 1，當i <= n時，更新（i增加1），執行以下操作：
- x := nums[i - 1]
- 初始化j := 0，當j < 2 * sum + 5時，更新（j增加1），執行以下操作：
- 如果j - x >= 0且dp[i - 1, j - x]不等於-1，則：
- dp[i, j] := dp[i, j]和(dp[i - 1, j - x] + x)中的最大值
- 如果j + x < (2 * sum + 5)且dp[i - 1, j + x]不等於-1，則：
- dp[i, j] := dp[i, j]和(dp[i - 1, j + x])中的最大值
- dp[i, j] := dp[i, j]和dp[i - 1, j]中的最大值
- 如果j - x >= 0且dp[i - 1, j - x]不等於-1，則：
- 返回dp[n, sum]
示例 (C++)
讓我們看看下面的實現以更好地理解：
#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);
}
main(){
vector<int> v = {2, 5, 4, 6};
cout << solve(v);
}輸入
{2, 5, 4, 6}輸出
6
更新於：2020年12月12日
95 次檢視
廣告