相关疑难解决方法(0)

假设我有一个数字S = [6,2,1,7,4,3,9,5,3,1]的数组.我想分成三个数组.数组的顺序和这些数组中的项目数无关紧要.

假设A1,A2和A3是子阵列.我想最小化功能

f(x) = ( SUM(A1) - SUM(S) / 3 )^2 / 3 +
       ( SUM(A2) - SUM(S) / 3 )^2 / 3 +
       ( SUM(A3) - SUM(S) / 3 )^2 / 3

• 我不需要最佳解决方案; 我只需要足够好的解决方案.
• 我不想要一个太慢的算法.我可以用一些速度换取更好的结果,但我不能交易太多.
• S的长度约为10至30.

为什么

为什么我需要解决这个问题？我希望将盒子很好地排列成三列,这样每列的总高度就不会相差太大.

我试过了什么

我的第一直觉是使用贪心.结果并不是那么糟糕,但它无法确保最佳解决方案.有没有更好的办法？

s = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1]
s = sorted(s, reverse=True)

a = [[], [], []]
sum_a = [0, 0, 0]

for x in s:
    i = sum_a.index(min(sum_a))
    sum_a[i] += x
    a[i].append(x) …

这是一个硬算法问题:

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

列表长度为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)较少.

等等...