8

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...

4

5 回答 5

7

您可以将其重新表述为背包问题。

您有一个总重量为 M 的物品清单，这些物品应装入可容纳最大重量 M/2 的箱子中。装入垃圾箱的物品应尽可能称重，但不要超过垃圾箱的重量。

对于所有权重都是非负的情况，这个问题只是弱 NP 完全的并且具有多项式时间解。

可以在Wikipedia上找到针对此问题的动态规划解决方案的描述。

于 2010-12-18T18:56:12.170 回答
4

问题是NPC，但是有一个伪多项式算法，这是一个2-Partition问题，您可以按照子集和问题的伪多项式时间算法的方式来解决这个问题。如果输入大小与输入值呈多项式相关，则可以在多项式时间内完成。

在您的情况下（权重 < 250）它是多项式（因为权重 <= 250 n => 总和 <= 250 n^2）。

令 Sum = 权重之和，我们要创建二维数组 A，然后逐列构造 A

A[i,j] = true if (j == weight[i] or j - weight[i] = weight[k] (k is in list))。

使用此算法创建数组需要 O(n^2 * sum/2)。

最后我们应该找到最有价值的列，它具有真正的价值。

这是一个例子：

项目：{0,1,2,3} 权重：{4,7,2,8} => sum = 21 sum/2 = 10

items/weights 0|  1  | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10    
  --------------------------------------------------------- 
  |0             |  0  | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0
  |1             |  0  | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0
  |2             |  0  | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1
  |3             |  0  | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1

所以因为 a[10, 2] == true 分区是 10, 11

这是我在这里找到的一种算法，并对其进行了一些编辑以解决您的问题：

bool partition( vector< int > C ) {
 // compute the total sum
 int n = C.size();
 int N = 0;
 for( int i = 0; i < n; i++ ) N += C[i];
 // initialize the table 
 T[0] = true;
 for( int i = 1; i <= N; i++ ) T[i] = false;
 // process the numbers one by one
 for( int i = 0; i < n; i++ )
  for( int j = N - C[i]; j >= 0; j--)
   if( T[j] ) T[j + C[i]] = true;

 for(int i = N/2;i>=0;i--)
    if (T[i])
      return i;
 return 0;
}

我只是返回了第一个 T[i] 这是真的，而不是返回 T[N/2] （从最大到最小的顺序）。

找到给出这个值的路径并不难。

于 2010-12-18T19:27:43.087 回答
2

这个问题至少和 NP 完全问题子集 sum一样难。你的算法是一个贪心算法。这种算法速度快，可以快速生成近似解，但无法找到 NP 完全问题的精确解。

蛮力方法可能是解决问题的最简单方法，尽管如果元素太多，它会变慢。

  • 尝试将元素分成两组的所有可能方法，并计算总和的绝对差。
  • 选择绝对差异最小的分区。

可以通过考虑从 0 到 2^n 的每个整数的二进制表示来生成所有分区，其中每个二进制数字确定对应元素是在左分区还是在右分区。

于 2010-12-18T18:54:07.703 回答
0

尝试解决相同的问题时，我遇到了以下想法，这似乎是一个太多的解决方案，但它在线性时间内起作用。是否可以提供一个示例来表明它不起作用或解释为什么它不是解决方案？

arr = [20,10,15,6,1,17,3,9,10,2,19] # a list of numbers

g1 = []
g2 = []

for el in reversed(sorted(arr)):
    if sum(g1) > sum(g2):
        g2.append(el)
    else:
        g1.append(el)

print(f"{sum(g1)}: {g1}")
print(f"{sum(g2)}: {g2}")
于 2021-04-20T18:42:30.787 回答
0

打字稿代码：

import * as _ from 'lodash'
function partitionArray(numbers: number[]): {
    arr1: number[]
    arr2: number[]
    difference: number
} {
    let sortedArr: number[] = _.chain(numbers).without(0).sortBy((x) => x).value().reverse()
    let arr1: number[] = []
    let arr2: number[] = []
    let median = _.sum(sortedArr) / 2
    let sum = 0

    _.each(sortedArr, (n) => {
        let ns = sum + n
        if (ns > median) {
            arr1.push(n)
        } else {
            sum += n
            arr2.push(n)
        }
    })
    return {
        arr1: arr1,
        arr2: arr2,
        difference: Math.abs(_.sum(arr1) - _.sum(arr2))
    }
}
于 2021-08-01T16:14:32.847 回答