问题标签 [partition-problem]

You can exempt atmost one element from the set to acheive the goal. example:-

N=3

the numbers given are = 1,2,5

So,

Set 1 should be :- [1]

Set 2 should be :- [2]

We have excluded 5 as we can acheive a lesser difference without it being in either groups.

N=4

numbers = 1,2,2,5

Set1 = [1,2,2]

Set2 = [5]

What is best algorithm for this? I know that this a NP-complete problem. And I think that brute force would give me the correct solution but I need an algorithm if available.

在编写程序第 2.3 章中，有一个函数 print_part() 让我感到困惑（此处为完整代码）：

此函数使用最多 4 个到分区 6 的部分打印所有方式。我了解分区算法在 partition_tree() 中的工作原理，并且理解分区树没有问题：

但我仍然不知道如何从分区树打印分区方式。特别是这些行：

更新：

这里的递归看起来不像 print_parts() 一开始调用的方式。

以一个更简单的 args 为例来说明我的困惑：

分区树是：

或者

上面的列表首先作为树的值传递给 func print_parts()。

当去这条线时：

左边的值为

它不再是一棵树，因为在定义中，树应该具有如下结构：[node, [branch],[branch]]。如果是这样，递归就不能工作。

给定一个数字列表 L = { a1, a2, a3, a4, ... , aN}

问题是将这个L分成两部分，不仅仅是一次，而是递归的，直到它变成原子的。主要思想就像这篇文章，但添加了递归的东西。

（添加：6 月 9 日） 例如，如果我们有 L = {10, 20, 1, 2} （编辑：6 月 10 日），解决方案可能是，首先，将其划分为 {10, 1, 2} 和​​ {20} ，然后将前者分为{1, 2}和{10}，继续与{1, 2}到{1}, {2}。现在 L 的所有成员现在都是原子的，不能再被划分了。

划分后，它应该看起来像某种二叉树。

假设它看起来像这样..

每个节点的相似度函数为

我想根据这个函数的“求和”找到一种“优化”的方式来划分列表（创建树）。请注意，在顶层，此值可能比较低的值具有更大的影响，因此应提供权重。

let level是该节点在二叉树中的级别。

我认为可以使用时间复杂度为 O(2^N) 的动态编程来解决这个问题。但是，这个解决方案对我来说似乎太慢了。有人有更好的解决方案吗？

也欢迎优化和近似。

先感谢您。

我有一个问题，说明如下：

给定一个数字序列 (S)、一个初始值 (V) 和一个目标值 (T)，检查是否存在可以分配给序列 S 的 + 和 - 操作序列（这些操作必须遵守序列顺序) 达到一个大于或等于 T 的数，从 V 开始。此外，有一个极限 X 不能在任何时候被打破（如果总和在任何时候离开区间 [0, X]，则该解决方案路径无效。问题中的所有数字也在这个区间内）。

此外，我必须找到可以从这些操作中获得的最大总和，遵守限制规则（如果 -last- 操作使总和超出限制，则可能会被破坏）。

我一直在研究它，并研究了一些关于背包问题和分区问题的动态规划解决方案，我相信解决方案会是这一行。

但是我不知道如何处理限制规则以及如何找到最大的总和。在某些情况下会出现极限问题：假设我试图找到一个背包解决方案来找到要相加的数字，其余的数字要减去。背包解决方案可以打破总和的上限，但实际总和可能不会因为操作的顺序（它可以在限制实际被打破之前减去一些东西，那么它就不会被打破全部）。

任何人都可以帮我找到一个好的方法吗？谢谢你。

我有以下任务。

您有一个包含 1<=N<=22 个元素的多重集 S。每个元素的正值最大为 10000000。

假设 S 有两个子集 s1 和 s2，其中一个的所有元素的值之和等于另一个的所有元素的值之和，并且它是可能的最大值。我必须返回 S 的哪些元素不会包含在两个子集中的任何一个中。

它之前可能已经解决了，我认为它是分区问题的一些变体，但我找不到它。如果有人能指出我正确的方向，那就太好了。

编辑：一个元素不能在两个子集中。

我有一组浮点值，我想将它们分成两组，其大小最多相差一个元素。此外，两组之间的价值总和的差异应该是最小的。可选地，如果元素的数量是奇数并且总和不能相等，则较小的集合应该具有较大的总和。

那将是最佳解决方案，但我只需要子集大小约束的精确解决方案。总和的差异并不需要非常小，但应该接近。我也希望较小的集合（如果有）具有较大的总和。

我意识到这可能与分区问题有关，但并不完全相同或严格。

我目前的算法如下，但我想知道是否有办法改进它：

我对这种方法的问题是我不确定实际的复杂性以及它是否可以改进。它当然不能满足将较小的子集留下较大的总和的要求。

是否有任何现有算法恰好可以实现我想要实现的目标？如果没有，你能建议我改进我的算法或找出它可能已经对这个问题有相当好的效果吗？

众所周知，分区问题是 NP 难的。根据问题的特定实例，我们可以尝试动态编程或一些启发式算法，如差分（也称为 Karmarkar-Karp 算法）。

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

PS：这个问题背后有一些故事。自 2004 年 7 月以来，SPOJ 提供了Johnny Goes Shopping的挑战。到目前为止，该挑战已被 1087 名用户解决，但其中只有 11 人的得分高于正确的 Karmarkar-Karp 算法实现（当前评分，Karmarkar-Karp 给出 11.796614点）。如何做得更好？（最想要的已接受提交支持的答案，但请不要透露您的代码。）

我正在尝试解决分区问题的变体。我有两个重要的转折。我需要解决 k 个分区，而不仅仅是 2 个，就像在经典分区问题中一样。

以下代码执行此操作：

https://gist.github.com/ishikawa/21680

我还需要允许自由地打乱项目的顺序，这样我才能得到最优的解决方案。因此，在经典问题要求元素的顺序保持完整，并且数组只是在半最佳点处拆分的情况下，我需要允许数组以这样的方式重新排序，即分区最小。

我该如何解决这个问题？对于这个现实世界的应用程序，这两种扭曲都是必要的。如果我能找到一个已经处理这个问题的 Java 库，我会非常高兴。

我正在解决一个对我来说看起来像分区问题的问题：我有一个整数序列，我应该找到这些整数的一个子集（如果有多个解决方案，我应该只输出一个），这样它们的总和正好是所有整数之和的一半。

我正在尝试通过动态编程来解决它，但是我的解决方案在测试中仍然太慢（我只能通过 2/10 的测试并且休息太慢）。感谢帮助。

我的代码：

我正在开发一个程序来解决 0/1 背包问题的变体。

此处描述了原始问题：https ://en.wikipedia.org/wiki/Knapsack_problem 。万一以后链接丢失了，我给大家总结一下 0/1 背包问题（如果你熟悉的话，跳过这一段）：假设我们有n物品，每个物品都有重量wi和价值vi。我们想把物品放在一个支持最大重量的袋子里，W这样袋子里的总价值就是最大可能的，而不会使袋子超重。项目不能有多个实例（即，我们每个实例只有一个）。问题的目的是maximize SUM(vi.xi)使SUM(wi.xi) <= W和xi = 0, 1（xi表示物品在袋子中或不在袋子中的状态）。

就我而言，条件和目标都存在细微差别：

• 所有物品的重量为1，wi = 1, i = 1...n

• 我总是想把一半的东西放在包里。因此，袋子的最大重量容量是物品数量的一半（四舍五入）。W = ceil[n/2]或W = floor[(n+1)/2]。

• 此外，包内的重量必须等于其最大容量SUM(wi.xi) = W

最后，不是最大化包内物品的价值，而是目标是内部物品的价值尽可能接近外面物品的价值。因此，我的目标是minimize |SUM(vi.-xi) - SUM[vi(1-xi)]|，它简化为minimize |SUM[vi(2xi - 1)]|.

现在，在上面的 Wikipedia 页面中有原始 0/1 背包问题的伪代码（您可以在本文底部找到它），但我无法将其适应我的场景。有人可以帮忙吗？（我不是要代码，只是为了一个想法，所以语言无关紧要）

谢谢！

维基百科的 0/1 背包问题的伪代码：

假设w1, w2, ..., wn, W是严格的正整数。定义 为在重量小于或等于使用最多（第一个项目）的项目时m[i,w]可以达到的最大值。wii

我们可以m[i,w]递归定义如下：

• m[0, w]=0
• m[i, w] = m[i-1, w] if wi > w（新品超过当前重量限制）
• m[i, w]= max(m[i-1, w], m[i-1, w-wi] + vi) if wi <= w.

然后可以通过计算找到解决方案m[n,W]。