首页 文章

将一组2n个整数划分为n个整数的两个子集，其总和为正

提问于
浏览 次
2

给定一组2n个整数，是否可以在n个整数的两个子集中找到一个分区，每个子集的总和为正 .

我的想法：我们表示集合v [1]，...，v [2n]的值 . 如果存在该组的前j个整数的分区分别为k和jk整数的两个子集，则设S [j，k，s1，s2] = 1，使得第一子集总和为s1，第二子集求和到s2 . （s1和s2当然可以是否定的）

我们有以下关系：S [j 1，k，s1，s2] = 1 iff S [j，k-1，s1-v [j 1]，s2] = 1或S [j，k，s1，s2 -v [j 1]] . 原因是你必须添加* j 1 th " element to either the " first " subset or the " second“ .

如果s1_0> 0且s2_0> 0使得S [2n，n，s1_0，s2_0] = 1，则问题的答案为是 .

你怎么看？有没有更好的方法（在时间/空间复杂性方面）？我从一开始就假设这是一个动态编程问题，还有其他方法吗？

algorithm dynamic-programming

1 回答

  • 0

    不是动态编程，但仍然是一个想法 .

    let A and B be two empty sets

sort v
for i in [0, 2, ..., 2n)
    // note that v[i] <= v[i + 1]
    assign v[i] to the set with the largest sum
    assign v[i + 1] to the set with the smallest sum

return sum(A) >= 0 and sum(B) >= 0

    我们的想法是尽可能均匀地分配数字，并限制负数造成的损害，同时保持集合的基数相同

    • 当两组都有负数时，数字被分配，使得它们的总和尽可能减少

    • 当正好一组具有正总和时，最大数字将被分配给具有负和的集合

    • 当两组都有正数时，任何作业都没有问题

    回复于

相关问题