具有最大相等和且不使用所有元素的子集和
Subset sum with maximum equal sums and without using all elements
给你一组整数，你的任务如下：将它们分成 2 个总和相等的子集，以使这些总和最大。您可以不使用所有给定的整数，这没关系。如果不可能，请以某种方式报告错误。
我的方法相当简单：在每一步中，我们选择一个项目，将其标记为已访问，更新当前总和并递归地选择另一个项目。最后，尝试跳过当前元素。
它适用于更简单的测试用例，但它失败了一个：
T = 1
N = 25
Elements: 5 27 24 12 12 2 15 25 32 21 37 29 20 9 24 35 26 8 31 5 25 21 28 3 5
可以运行如下：
1 25 5 27 24 12 12 2 15 25 32 21 37 29 20 9 24 35 26 8 31 5 25 21 28 3 5
我希望总和等于 239，但算法找不到这样的解。
我得到了以下代码：
#include <iostream>
#include <unordered_set>
using namespace std;
unordered_set<uint64_t> visited;
const int max_N = 50;
int data[max_N];
int p1[max_N];
int p2[max_N];
int out1[max_N];
int out2[max_N];
int n1 = 0;
int n2 = 0;
int o1 = 0;
int o2 = 0;
int N = 0;
void max_sum(int16_t &sum_out, int16_t sum1 = 0, int16_t sum2 = 0, int idx = 0) {
if (idx < 0 || idx > N) return;
if (sum1 == sum2 && sum1 > sum_out) {
sum_out = sum1;
o1 = n1;
o2 = n2;
for(int i = 0; i < n1; ++i) {
out1[i] = p1[i];
}
for (int i = 0; i < n2; ++i) {
out2[i] = p2[i];
}
}
if (idx == N) return;
uint64_t key = (static_cast<uint64_t>(sum1) << 48) | (static_cast<uint64_t>(sum2) << 32) | idx;
if (visited.find(key) != visited.end()) return;
visited.insert(key);
p1[n1] = data[idx];
++n1;
max_sum(sum_out, sum1 + data[idx], sum2, idx + 1);
--n1;
p2[n2] = data[idx];
++n2;
max_sum(sum_out, sum1, sum2 + data[idx], idx + 1);
--n2;
max_sum(sum_out, sum1, sum2, idx + 1);
}
int main() {
int T = 0;
cin >> T;
for (int t = 1; t <= T; ++t) {
int16_t sum_out;
cin >> N;
for(int i = 0; i < N; ++i) {
cin >> data[i];
}
n1 = 0;
n2 = 0;
o1 = 0;
o2 = 0;
max_sum(sum_out);
int res = 0;
int res2 = 0;
for (int i = 0; i < o1; ++i) res += out1[i];
for (int i = 0; i < o2; ++i) res2 += out2[i];
if (res != res2) cerr << "ERROR: " << "res1 = " << res << "; res2 = " << res2 << '\n';
cout << "#" << t << " " << res << '\n';
visited.clear();
}
}
我有以下问题：
- 有人可以帮我解决失败的测试吗？有什么明显的问题吗？
- 我怎样才能去掉 unordered_set 来标记已经访问过的总和？我更喜欢使用纯 C.
- 有没有更好的方法？也许使用动态规划？
1) 有人可以帮我解决失败的测试吗？有什么明显的问题吗？
我能看到的唯一问题是您没有将 sum_out 设置为 0。
当我尝试 运行 该程序时，它似乎对您的测试用例正常工作。
2) 我怎样才能去掉 unordered_set 来标记已经访问过的总和？我更喜欢使用纯 C.
查看问题 3 的答案
3) 有更好的方法吗？也许使用动态规划？
您目前正在记录您是否看到了 value for first subset、value for second subset、amount through array 的每个选项。
如果您改为跟踪值之间的差异，那么复杂性会大大降低。
特别是，您可以使用动态规划来存储数组 A[diff]，对于差值的每个值，要么存储 -1（表示差值不可达到），要么存储 subset1 的最大值，当subset1 和 subset2 的差正好等于 diff.
然后您可以遍历输入中的条目并根据将每个元素分配给 subset1/subset2/ 或根本不分配来更新数组。 （请注意，您需要在计算此更新时制作数组的新副本。）
在这种形式中没有使用 unordered_set 因为你可以简单地使用一个直接的 C 数组。 subset1 和 subset2 之间也没有区别，所以你只能保持正差异。
示例Python代码
from collections import defaultdict
data=map(int,"5 27 24 12 12 2 15 25 32 21 37 29 20 9 24 35 26 8 31 5 25 21 28 3 5".split())
A=defaultdict(int) # Map from difference to best value of subset sum 1
A[0] = 0 # We start with a difference of 0
for a in data:
A2 = defaultdict(int)
def add(s1,s2):
if s1>s2:
s1,s2=s2,s1
d = s2-s1
if d in A2:
A2[d] = max( A2[d], s1 )
else:
A2[d] = s1
for diff,sum1 in A.items():
sum2 = sum1 + diff
add(sum1,sum2)
add(sum1+a,sum2)
add(sum1,sum2+a)
A = A2
print A[0]
这将打印 239 作为答案。
为了简单起见，我没有考虑使用线性数组而不是字典进行优化。
一种非常不同的方法是使用约束或混合整数求解器。这是一个可能的公式。
让
x(i,g) = 1 if value v(i) belongs to group g
0 otherwise
优化模型如下所示：
max s
s = sum(i, x(i,g)*v(i)) for all g
sum(g, x(i,g)) <= 1 for all i
对于两组我们得到：
---- 31 VARIABLE s.L = 239.000
---- 31 VARIABLE x.L
g1 g2
i1 1
i2 1
i3 1
i4 1
i5 1
i6 1
i7 1
i8 1
i9 1
i10 1
i11 1
i12 1
i13 1
i14 1
i15 1
i16 1
i17 1
i18 1
i19 1
i20 1
i21 1
i22 1
i23 1
i25 1
我们可以轻松地做更多的组。例如。 9 组：
---- 31 VARIABLE s.L = 52.000
---- 31 VARIABLE x.L
g1 g2 g3 g4 g5 g6 g7 g8 g9
i2 1
i3 1
i4 1
i5 1
i6 1
i7 1
i8 1
i9 1
i10 1
i11 1
i12 1
i13 1
i14 1
i15 1
i16 1
i17 1
i19 1
i20 1
i21 1
i22 1
i23 1
i24 1
i25 1
如果没有解，求解器将 select 将每个组中的元素归零，总和 s=0。
另一种方法是考虑 [1,(2^N-2)] 之前的所有数字。
考虑每个位到每个元素位置的位置。迭代 [1,(2^N-2)] 中的所有数字，然后检查每个数字。
如果设置了位，您可以在 set1 中计算该数字，否则您可以将该数字放入 set2，然后检查两组的总和是否相等。在这里你会得到所有可能的集合，如果你只想要一个，一旦你发现刚刚打破。
给你一组整数，你的任务如下：将它们分成 2 个总和相等的子集，以使这些总和最大。您可以不使用所有给定的整数，这没关系。如果不可能，请以某种方式报告错误。
我的方法相当简单：在每一步中，我们选择一个项目，将其标记为已访问，更新当前总和并递归地选择另一个项目。最后，尝试跳过当前元素。
它适用于更简单的测试用例，但它失败了一个：
T = 1
N = 25
Elements: 5 27 24 12 12 2 15 25 32 21 37 29 20 9 24 35 26 8 31 5 25 21 28 3 5
可以运行如下：
1 25 5 27 24 12 12 2 15 25 32 21 37 29 20 9 24 35 26 8 31 5 25 21 28 3 5
我希望总和等于 239，但算法找不到这样的解。
我得到了以下代码：
#include <iostream>
#include <unordered_set>
using namespace std;
unordered_set<uint64_t> visited;
const int max_N = 50;
int data[max_N];
int p1[max_N];
int p2[max_N];
int out1[max_N];
int out2[max_N];
int n1 = 0;
int n2 = 0;
int o1 = 0;
int o2 = 0;
int N = 0;
void max_sum(int16_t &sum_out, int16_t sum1 = 0, int16_t sum2 = 0, int idx = 0) {
if (idx < 0 || idx > N) return;
if (sum1 == sum2 && sum1 > sum_out) {
sum_out = sum1;
o1 = n1;
o2 = n2;
for(int i = 0; i < n1; ++i) {
out1[i] = p1[i];
}
for (int i = 0; i < n2; ++i) {
out2[i] = p2[i];
}
}
if (idx == N) return;
uint64_t key = (static_cast<uint64_t>(sum1) << 48) | (static_cast<uint64_t>(sum2) << 32) | idx;
if (visited.find(key) != visited.end()) return;
visited.insert(key);
p1[n1] = data[idx];
++n1;
max_sum(sum_out, sum1 + data[idx], sum2, idx + 1);
--n1;
p2[n2] = data[idx];
++n2;
max_sum(sum_out, sum1, sum2 + data[idx], idx + 1);
--n2;
max_sum(sum_out, sum1, sum2, idx + 1);
}
int main() {
int T = 0;
cin >> T;
for (int t = 1; t <= T; ++t) {
int16_t sum_out;
cin >> N;
for(int i = 0; i < N; ++i) {
cin >> data[i];
}
n1 = 0;
n2 = 0;
o1 = 0;
o2 = 0;
max_sum(sum_out);
int res = 0;
int res2 = 0;
for (int i = 0; i < o1; ++i) res += out1[i];
for (int i = 0; i < o2; ++i) res2 += out2[i];
if (res != res2) cerr << "ERROR: " << "res1 = " << res << "; res2 = " << res2 << '\n';
cout << "#" << t << " " << res << '\n';
visited.clear();
}
}
我有以下问题：
- 有人可以帮我解决失败的测试吗？有什么明显的问题吗？
- 我怎样才能去掉 unordered_set 来标记已经访问过的总和？我更喜欢使用纯 C.
- 有没有更好的方法？也许使用动态规划？
1) 有人可以帮我解决失败的测试吗？有什么明显的问题吗？
我能看到的唯一问题是您没有将 sum_out 设置为 0。
当我尝试 运行 该程序时，它似乎对您的测试用例正常工作。
2) 我怎样才能去掉 unordered_set 来标记已经访问过的总和？我更喜欢使用纯 C.
查看问题 3 的答案
3) 有更好的方法吗？也许使用动态规划？
您目前正在记录您是否看到了 value for first subset、value for second subset、amount through array 的每个选项。
如果您改为跟踪值之间的差异，那么复杂性会大大降低。
特别是，您可以使用动态规划来存储数组 A[diff]，对于差值的每个值，要么存储 -1（表示差值不可达到），要么存储 subset1 的最大值，当subset1 和 subset2 的差正好等于 diff.
然后您可以遍历输入中的条目并根据将每个元素分配给 subset1/subset2/ 或根本不分配来更新数组。 （请注意，您需要在计算此更新时制作数组的新副本。）
在这种形式中没有使用 unordered_set 因为你可以简单地使用一个直接的 C 数组。 subset1 和 subset2 之间也没有区别，所以你只能保持正差异。
示例Python代码
from collections import defaultdict
data=map(int,"5 27 24 12 12 2 15 25 32 21 37 29 20 9 24 35 26 8 31 5 25 21 28 3 5".split())
A=defaultdict(int) # Map from difference to best value of subset sum 1
A[0] = 0 # We start with a difference of 0
for a in data:
A2 = defaultdict(int)
def add(s1,s2):
if s1>s2:
s1,s2=s2,s1
d = s2-s1
if d in A2:
A2[d] = max( A2[d], s1 )
else:
A2[d] = s1
for diff,sum1 in A.items():
sum2 = sum1 + diff
add(sum1,sum2)
add(sum1+a,sum2)
add(sum1,sum2+a)
A = A2
print A[0]
这将打印 239 作为答案。
为了简单起见，我没有考虑使用线性数组而不是字典进行优化。
一种非常不同的方法是使用约束或混合整数求解器。这是一个可能的公式。
让
x(i,g) = 1 if value v(i) belongs to group g
0 otherwise
优化模型如下所示：
max s
s = sum(i, x(i,g)*v(i)) for all g
sum(g, x(i,g)) <= 1 for all i
对于两组我们得到：
---- 31 VARIABLE s.L = 239.000
---- 31 VARIABLE x.L
g1 g2
i1 1
i2 1
i3 1
i4 1
i5 1
i6 1
i7 1
i8 1
i9 1
i10 1
i11 1
i12 1
i13 1
i14 1
i15 1
i16 1
i17 1
i18 1
i19 1
i20 1
i21 1
i22 1
i23 1
i25 1
我们可以轻松地做更多的组。例如。 9 组：
---- 31 VARIABLE s.L = 52.000
---- 31 VARIABLE x.L
g1 g2 g3 g4 g5 g6 g7 g8 g9
i2 1
i3 1
i4 1
i5 1
i6 1
i7 1
i8 1
i9 1
i10 1
i11 1
i12 1
i13 1
i14 1
i15 1
i16 1
i17 1
i19 1
i20 1
i21 1
i22 1
i23 1
i24 1
i25 1
如果没有解，求解器将 select 将每个组中的元素归零，总和 s=0。
另一种方法是考虑 [1,(2^N-2)] 之前的所有数字。 考虑每个位到每个元素位置的位置。迭代 [1,(2^N-2)] 中的所有数字，然后检查每个数字。 如果设置了位，您可以在 set1 中计算该数字，否则您可以将该数字放入 set2，然后检查两组的总和是否相等。在这里你会得到所有可能的集合，如果你只想要一个，一旦你发现刚刚打破。