标签: partition-problem

可能重复:
最佳地聚类一维数据？

所以,假设我有一个这样的数组:

[1,1,2,3,10,11,13,67,71]

有没有一种方便的方法将数组分区为这样的东西？

[[1,1,2,3],[10,11,13],[67,71]]

我查看了类似的问题,但是大多数人建议使用k-means来聚集点,比如scipy,这对像我这样的初学者来说非常混乱.另外我认为k-means更适合两维或更多维聚类吧？有没有办法根据数字将N个数组分组到多个分区/聚类？

有些人还提出了严格的范围分区,但并不总是按预期呈现结果

已知分区问题是NP难的.根据问题的具体情况,我们可以尝试动态编程或一些启发式方法,如差分(也称为Karmarkar-Karp算法).

后者似乎对于具有大数字的实例(使动态编程难以处理)非常有用,但并不总是完美的.什么是找到更好的解决方案的有效方法(随机,禁忌搜索,其他近似)？

PS:问题背后有一些故事.自2004年7月以来,SPOJ就迎来了挑战Johnny Goes Shopping.到目前为止,1087个用户已经解决了这个挑战,但只有11个用户得分高于正确的Karmarkar-Karp算法(目前得分,Karmarkar-Karp给出了11.796614)点).怎么做得更好？(最受欢迎的已接受提交支持的答案,但请不要透露您的代码.)

这是另一个动态编程问题(Vazirani ch6)

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

sum(I)= sum(J)= sum(K)= 1/3*sum(ALL)

例如,对于输入(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分区但仍然无法解决它

这是一个硬算法问题:

将列表分成两部分(总和),它们的总和最接近(大多数)彼此

列表长度为1 <= n <= 100且问题中给出的(数字)权重1 <= w <= 250.

例如:23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

我有一个算法,但它并不适用于所有输入.

1. 在里面.列表list1 = [],list2 = []
2. 排序元素(给定列表)[23 32 34 65 95 123 134]
3. 弹出最后一个(最多一个)
4. 插入到不同的列表中

实现:list1 = [],list2 = []

1. 选择134插入列表1.list1 = [134]
2. 选择123插入列表2.因为如果你插入list1差异越来越大
   3.选择95并插入list2.因为sum(list2)+ 95 - sum(list1)较少.

等等...

我正在为android制作一个数学应用程序.在其中一个字段中,用户可以输入int(无数字且高于0).这个想法是获得所有可能的和,使得这个int,没有双打(在这种情况下4 + 1 == 1 + 4).唯一知道的是这一个int.

例如:

假设用户输入4,我希望应用程序返回:

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

显然4 == 4所以也应该加上.关于我应该如何做这个的任何建议？

嘿,我正在寻找一些帮助来找到一个算法,将一组正数分成k部分,这样每个部分都有(大约)相同的总和...让我们说我们有

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

Annyone得到了什么提示？

我对理解动态编程有困难,所以我决定解决一些问题.我知道基本的动态算法,如最长的常见子序列,背包问题,但我知道它们因为我读过它们,但我不能自己想出一些东西:-(

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

in1:10 3 5 4; out1:2

in2:4 11 5 5 5; out2:0

in3:10 50 60 65 90 100; out3:5

第3次解释:5 = | 10 + 50 + 60 + 65-90-100 |

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

我一直在研究一些算法编程问题并且有一个问题.问题与此问题中引用的问题相同:USACO:子集(低效)

我能够编写一些(非动态)解决方案,这些解决方案对于高N来说太慢了.不得不作弊并在线查找一些解决方案.事实证明,快速算法很简单,但即使知道答案,我仍然无法看到如何从问题到答案.我可以看到相等和的子集形式的模式,但我没有看到这些模式和算法解决方案之间的联系.

问题(上面的链接)是:

给定一组从1到N的连续整数(1 <= N <= 39),可以将该组划分为两个总和相同的子集的方式有多少？例如,{1,2,3}可以单向划分:{1,2} {3}.

对于较大的集合,答案为0(当N*(N + 1)/ 2为奇数时)或由此简单算法给出:

  arr = array of int with (N*(N+1)/4)+1 elements
  arr[0]=1  // all other elements initialized to 0
  for i = 1 to N
    for j = N*(N+1) / 4 downto i
      add arr[j-i] to arr[j]
  subsetpaircount = arr[N*(N+1)/4] / 2

再次,我可以看到算法如何工作,我甚至插入了打印语句,所以我可以"观察"它是如何工作的.我只是看不出算法的操作如何链接到生成两组分区的不同方式的模式.

链接问题中的响应可能是相关的,但我也无法联系它是如何工作的:"这与在多项式中找到系数x ^ 0项(x ^ 1 + 1/x)(x)相同^ 2 + 1/x ^ 2)...(x ^ n + 1/x ^ n)......"

任何人都可以为我澄清这种联系,或者指出一些解释这个具体问题的参考资料？谢谢.

我过去曾经遇到过类似的问题,我仍然不知道如何解决这个问题.问题是这样的:

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

Input:                           Output:
5  3  >> n = 5 k = 3             3
2 1 1 2 3

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

我的强力想法是让第一个子阵列在位置i(对于所有可能的i)结束,然后尝试以尽可能最好的方式将数组的其余部分分成k-1个子阵列.但是,这是指数级解决方案,永远不会奏效.

所以我正在寻找好的想法来解决它.如果你有,请告诉我.

谢谢你的帮助.

我正在解决一个编程练习,并遇到了一个问题,我无法满意地找到解决方案.问题如下:

Print all unique integer partitions given an integer as input.
Integer partition is a way of writing n as a sum of positive integers.

例如:输入= 4然后输出应为输出=

  1 1 1 1
  1 1 2
  2 2
  1 3
  4

我该如何考虑解决这个问题？我想知道使用递归.任何人都可以为我提供这个问题的算法吗？或暗示解决方案.对这类问题的任何解释都是受欢迎的.(我是编程世界的初学者)谢谢!!