问题标签 [partition-problem]

This is a hard algorithms problem that :

Divide the list in 2 parts (sum) that their sum closest to (most) each other

list length is 1 <= n <= 100 and their(numbers) weights 1<=w<=250 given in the question.

For example : 23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

I have an algorithm but it didn't work for all inputs.

1. init. lists list1 = [], list2 = []
2. Sort elements (given list) [23 32 34 65 95 123 134]
3. pop last one (max one)
4. insert to the list which differs less

Implementation : list1 = [], list2 = []

1. select 134 insert list1. list1 = [134]
2. select 123 insert list2. because if you insert to the list1 the difference getting bigger
   3. select 95 and insert list2 . because sum(list2) + 95 - sum(list1) is less.

and so on...

这是另一个动态编程问题（Vazirani ch6）

考虑以下 3-PARTITION 问题。给定整数 a1...an，我们想确定是否可以将 {1...n} 划分为三个不相交的子集 I、J、K，使得

和(I) = 和(J) = 和(K) = 1/3*和(全部)

例如，对于输入 (1; 2; 3; 4; 4; 5; 8)，答案是肯定的，因为存在分区 (1; 8), (4; 5), (2; 3; 4)。另一方面，对于输入 (2; 2; 3; 5)，答案是否定的。设计和分析 3-PARTITION 的动态规划算法，该算法在 n 和 (Sum a_i) 的时间多项式中运行

我怎么解决这个问题？我知道 2-partition 但仍然无法解决它

Given a set A containing n positive integers, how can I find the smallest integer >= 0 that can be obtained using all the elements in the set. Each element can be can be either added or subtracted to the total. Few examples to make this clear.

A = [ 2, 1, 3]

Result = 0 (2 + 1 - 3)

A = [1, 2, 0]

Result = 1 (-1 + 2 + 0)

A = [1, 2, 1, 7, 6]

Result = 1 (1 + 2 - 1 - 7 + 6)

嘿，我正在寻找一些帮助来找到一种算法，该算法将正数数组划分为 k 部分，以便每个部分具有（大约）相同的总和......假设我们有

1,2,3,4,5,6,7,8,9 en k=3 那么算法应该像这样划分它 1,2,3,4,5|6,7|8,9 的顺序元素不能改变......找到一个贪心算法很容易，但我正在寻找一个回溯版本，它总是返回最佳解决方案......

有人有任何提示吗？

我正在为安卓制作一个数学应用程序。在这些字段之一中，用户可以输入一个 int（无数字且大于 0）。这个想法是得到所有可能的总和，使这个整数，没有双打（在这种情况下为 4+1 == 1+4）。唯一知道的是这个int。

例如：

假设用户输入 4，我希望应用返回：

• 4
• 3+1
• 2+2
• 2+1+1
• 1+1+1+1

显然 4 == 4 所以也应该添加。关于我应该如何去做这件事的任何建议？

我想用近似偶数行来划分矩阵。例如，如果我有一个这些尺寸为 155 x 1000 的矩阵，我如何将它划分为 10，而每个新矩阵的尺寸约为 15 X 1000？

我是 Java 的新手。我正在编写一个 Android 游戏，我需要生成一个 int 数组数组，其中包含所有可能的总和（不包括包含数字 2 或大于 8 个数字的组合），它们加起来等于给定的数字。

例如： ganeratePatterns(5)必须返回数组

我已经尝试像那里那样做得到所有可能的总和加起来给定 的数字，但我很难做到像这样http://introcs.cs.princeton.edu/java/23recursion/Partition.java。 html

解决方案

它的工作不是 100% 正确，而且非常漂亮，但对于我的游戏来说已经足够了

我从这里使用 SumIterator 类SumIterator.class 我必须将此代码更改为此for(int j = n-1; j > n/2; j--) {，for(int j = n-1; j >= n/2; j--) {因为旧版本不会返回所有组合（例如 [5,5] for 10）

而且我使用了 toIntArray 函数。我在 StackOverflow 上创建了 hare，但忘记了链接，所以这里是它的来源：

我们正在为异构计算做一个调度程序。

这些任务可以通过它们的截止日期和它们的数据速率来识别，并且可以被视为一个二维图。见图片：

矩形标识要在 GPU 上调度的任务，以及要在 CPU 上调度的外部任务。

问题是我们想要有效地识别创建最佳矩形的参数。即包含大多数任务的矩形。可以假定存在确定是否可以将点添加到当前矩形的函数。

最多可以有 20.000 个（点）任务，轴可以是任意长度

是否有任何已知的算法/数据结构可以解决这个问题？

我过去遇到过一些与此类似的问题，但我仍然不知道如何解决这个问题。问题是这样的：

您将获得一个大小为 n <= 1000 且 k <= n 的正整数数组，这是您必须将数组拆分成的连续子数组的数量。您必须输出最小值 m，其中 m = max{s[1],..., s[k]}，并且 s[i] 是第 i 个子数组的总和。数组中的所有整数都在 1 到 100 之间。示例：

将数组拆分为 2+1 | 1+2 | 3将最小化m。

我的蛮力想法是使第一个子数组在位置 i 结束（对于所有可能的 i），然后尝试以可能的最佳方式将数组的其余部分拆分为 k-1 个子数组。但是，这是指数解决方案，永远不会奏效。

所以我正在寻找解决它的好主意。如果你有请告诉我。

谢谢你的帮助。

我在理解动态编程方面遇到了困难，所以我决定解决一些问题。我知道基本的动态算法，如最长公共子序列、背包问题，但我知道它们是因为我读过它们，但我自己无法想出一些东西:-(

例如，我们有自然数的子序列。我们可以用加号或减号取的每个数字。最后我们取这个总和的绝对值。对于每个子序列，找到可能的最低结果。

in1：10 3 5 4；输出1：2

in2：4 11 5 5 5；输出2：0

in3：10 50 60 65 90 100；输出3：5

第三个解释：5 = |10+50+60+65-90-100|

更糟糕的是我的朋友告诉我这是简单的背包问题，但我在这里看不到任何背包。动态编程是困难的还是只有我有大问题？