寻找符合约束条件的列表子集算法

Question

寻找符合约束条件的列表子集算法

pythonalgorithmmathgraphtree

4

我正在寻找一种高效的算法来执行以下任务。使用Python实现最佳，但使用其他语言或伪代码也会有所帮助。

给定一个有理数x和约600个有理数的列表。我想要从该列表中找到一个包含10个数字（不重复）的子集，满足以下约束条件：

s = x的总和加上子集中数字的总和

使得s与最近的整数之间的绝对差小于10e-12。

我猜这可能可以用某种图形算法来完成，但我不知道如何做到这一点。

示例：这是一种天真的方法，用于说明我正在寻找的内容。显然，这种方法对于在描述中给出的那么大的列表和子集的所有可能组合来说效率太低了。

#!/bin/python3

import sys
from math import pow
from itertools import combinations

x = 0.5
list = [1.000123,2.192,3.2143124,1.00041,2.0043,3.5]
for c in combinations(list,3):
    s = x + sum(c)
    r = s%1    
    if r <= pow(10,-3) or r >= 1-pow(10,-3):
        print("Found combination: s=%s for %s"%(s,c))
        break

示例输出：

找到组合：s=6.000533，对应（1.000123，1.00041，3.5）

- John Puccino

它们都是正数吗？它们可以有多大/小？与其他数字相比，x 有多大？ - Blender

@PaulPanzer：你说得对，谢谢。 - Blender

大声思考：您可以通过从所有数字中减去 x/10 来完全消除问题中的 x。这样，只需要知道如何解决“从集合中找到10个数字，使它们的总和几乎为整数”即可。 - avysk

@Blender：10-SUM是什么？你能提供一个链接吗？当我谷歌N-SUM时，没有相关的结果。 - B. Decoster

因为混合整数规划的运行效果不如我预期，我得到了这个列表的一个解，其值为 4.10^-10：

[0.6491106406735181, 0.8284271247461903, 0.8309518948453007, 0.038404810405298306, 0.08276253029821934, 0.08304597359457233, 0.16227766016837952, 0.36931687685298087, 0.45362404707370985, 0.48528137423856954, 0.4868329805051381]

。当你把它和 x 相加时，得到的是 4.999999999543545。 - B. Decoster

显示剩余7条评论

3个回答

2

以下是使用numpy的启发式解决方案。

更新：请原谅我的自夸，但请务必不要错过本文末尾，在k = 80个项的N = 1200个数字中以10 ^ -12的精度解决。该求解器在适度硬件上仅需4秒多一点就可以找到100多个解决方案。

算法（对于N = 600、k = 10、eps = 10 ^ -12的情况）：

它利用了有很多很多解的统计学特性，并且仅对可管理的子空间进行采样。

实际上，如果样本均匀分布，则只需要随机测试4x10 ^ 12个和即可有超过99.9％的概率找到解决方案。这可以通过将其拆分为2x10 ^ 6半和集合来达到可处理的级别，因为可以避免使用一个技巧来计算大多数成对和，该技巧仅涉及排序4x10 ^ 6个数字，这在当前硬件上可以轻松完成。

它的工作原理如下。

它选择30个不相交的随机子样本中的10个（可以降至20并仍然可以确信地找到解决方案），将它们分成两部分，并为每半计算所有30 ** 5个总和。然后从输入x的负数中减去其中一个半数。然后将所有内容按模1缩小并排序。

相邻元素之间的差异通常低于10 ^ -12的公差约2000，其中一半在来自不同半部分的总和之间。所有这些都是解决方案。

代码的大部分复杂性归功于追溯间接排序。

import numpy as np
import time

def binom(N, k):
    return np.prod(np.arange(N, N-k, -1).astype(object)) \
        // np.prod(np.arange(2, k+1).astype(object))

def master(nlist, input, k=10, HS=10**7, eps=12, ntrials=10):
    for j in range(ntrials):
        res = trial(nlist, input, k=k, HS=HS, eps=eps)
        if not res is None:
            return res
     print("No solution found in", ntrials, "trials.")

def trial(nlist, input, k=10, HS=10**7, eps=12):
    tol = 10**-eps
    srps = str(eps)
    t0 = time.time()
    N = len(nlist)
    if 2**(k//2) > HS or k > 64:
        kk = min(2 * int (np.log(HS) / np.log(2)), 64)
    else:
        kk = k        
    kA, kB = (kk+1)//2, kk//2
    CA = min(int(HS**(1/kA)), (N+kk-k) // (kA+kB))
    CB = min(int(HS**(1/kB)), (N+kk-k) // (kA+kB))
    inds = np.random.permutation(N)
    indsA = np.reshape(inds[:kA*CA], (kA, CA))
    indsB = np.reshape(inds[kA*CA:kA*CA+kB*CB], (kB, CB))
    extra = inds[N-k+kk:]
    A = sum(np.ix_(*tuple(nlist[indsA]))).ravel() % 1
    B = (-input - nlist[extra].sum()
         - sum(np.ix_(*tuple(nlist[indsB]))).ravel()) % 1
    AB = np.r_[A, B]
    ABi = np.argsort(AB)
    AB = np.where(np.diff(AB[ABi]) < tol)[0]
    nsol = len(AB)
    if nsol == 0:
        return None
     # translate back ...
    ABl = ABi[AB]
    ABh = ABi[AB+1]
    ABv = (ABl >= CA**kA) != (ABh >= CA**kA)
    nsol = np.count_nonzero(ABv)
    if nsol == 0:
        return None
    ABl, ABh = ABl[ABv], ABh[ABv]
    Ai = np.where(ABh >= CA**kA, ABl, ABh)
    Bi = np.where(ABh < CA**kA, ABl, ABh) - CA**kA
    Ai = np.unravel_index(Ai, kA * (CA,))
    Bi = np.unravel_index(Bi, kB * (CB,))
    solutions = [np.r_[indsA[np.arange(kA), Aii],
                       indsB[np.arange(kB), Bii], extra]
                 for Aii, Bii in zip(np.c_[Ai], np.c_[Bi])]
    total_time = time.time() - t0
    for sol in solutions:
        print(("{:."+srps+"f}  =  {:."+srps+"f}  " + "\n".join([
            j * (" + {:."+srps+"f}") for j
            in np.diff(np.r_[0, np.arange(4, k, 6), k])])).format(
                   nlist[sol].sum() + input, input, *nlist[sol]))
    print("\n{} solutions found in {:.3f} seconds, sampling {:.6g}% of"
          " available space.".format(nsol, total_time,
                                     100 * (CA**kA + CB**kB) / binom(N, k)))
    return solutions

输出：

a = np.random.random(600)
b = np.random.random()
s = trial(a, b)
...
<  --   snip   --  >
...
5.000000000000  =  0.103229509601  + 0.006642137376 + 0.312241735755 + 0.784266426461 + 0.902345822935 + 0.988978878589
 + 0.973861938944 + 0.191460799437 + 0.131957251738 + 0.010524218878 + 0.594491280285
5.999999999999  =  0.103229509601  + 0.750882954181 + 0.365709602773 + 0.421458098864 + 0.767072742224 + 0.689495123832
 + 0.654006237725 + 0.418856927051 + 0.892913889958 + 0.279342774349 + 0.657032139442
6.000000000000  =  0.103229509601  + 0.765785564962 + 0.440313432133 + 0.987713329856 + 0.785837107607 + 0.018125214584
 + 0.742834214592 + 0.820268051141 + 0.232822918386 + 0.446038517697 + 0.657032139442
5.000000000001  =  0.103229509601  + 0.748677981958 + 0.708845535002 + 0.330115345473 + 0.660387831821 + 0.549772082712
 + 0.215300958403 + 0.820268051141 + 0.258387204727 + 0.010524218878 + 0.594491280285
5.000000000001  =  0.103229509601  + 0.085365104308 + 0.465618675355 + 0.197311784789 + 0.656004057436 + 0.595032922699
 + 0.698000899403 + 0.546925212167 + 0.844915369567 + 0.333326991548 + 0.474269473129

1163 solutions found in 18.431 seconds, sampling 0.000038% of available space.

因为只使用了简单的操作，所以我们基本上只受浮点精度的限制。因此，让我们要求10^-14：

...
<  --   snip   --  >
...
6.00000000000000  =  0.25035941161807  + 0.97389388071258 + 0.10625051346950 + 0.59833873712725 + 0.89897827417947
 + 0.78865856416474 + 0.35381392162358 + 0.87346871541364 + 0.53658653353249 + 0.21248261924724 + 0.40716882891145
5.00000000000000  =  0.25035941161807  + 0.24071288846314 + 0.48554094441439 + 0.50713200488770 + 0.38874292843933
 + 0.86313933327877 + 0.90048328572856 + 0.49027844783527 + 0.23879340585229 + 0.10277432242557 + 0.53204302705691
5.00000000000000  =  0.25035941161807  + 0.38097649901116 + 0.48554094441439 + 0.46441170824601 + 0.62826547862002
 + 0.86313933327877 + 0.33939826575779 + 0.73873418282621 + 0.04398883198337 + 0.62252491844691 + 0.18266042579730
3.00000000000000  =  0.25035941161807  + 0.06822167273996 + 0.23678340695986 + 0.46441170824601 + 0.08855356615846
 + 0.00679943782685 + 0.74823208211878 + 0.56709685813503 + 0.44549706663049 + 0.05232395855097 + 0.07172083101554
4.99999999999999  =  0.25035941161807  + 0.02276077008953 + 0.29734365315824 + 0.74952397467956 + 0.74651313615300
 + 0.06942795892486 + 0.33939826575779 + 0.28515053127059 + 0.75198496353405 + 0.95549430775741 + 0.53204302705691
6.00000000000000  =  0.25035941161807  + 0.87635507011986 + 0.24113470302798 + 0.37942029808604 + 0.08855356615846
 + 0.30383588785334 + 0.79224372764376 + 0.85138208150978 + 0.76217062127440 + 0.76040834996762 + 0.69413628274069
5.00000000000000  =  0.25035941161807  + 0.06822167273996 + 0.51540640390940 + 0.91798512102932 + 0.63568890016512
 + 0.75300966489960 + 0.30826232152132 + 0.54179156374890 + 0.30349257203507 + 0.63406153731771 + 0.07172083101554

11 solutions found in 18.397 seconds, sampling 0.000038% of available space.

或者我们可以减少样本数量以获得更快的执行时间：

...
<  --   snip   -- >
...
4.999999999999  =  0.096738768432  + 0.311969906774 + 0.830155028676 + 0.164375548024 + 0.118447437942
 + 0.362452121111 + 0.676458354204 + 0.627931895727 + 0.568131437959 + 0.579341106837 + 0.663998394313
5.000000000000  =  0.096738768432  + 0.682823940439 + 0.768308425728 + 0.290242415733 + 0.303087635772
 + 0.776829608333 + 0.229947280121 + 0.189745700730 + 0.469824524584 + 0.795706660727 + 0.396745039400
6.000000000000  =  0.096738768432  + 0.682823940439 + 0.219502575013 + 0.164375548024 + 0.853518966685
 + 0.904544718964 + 0.272487275000 + 0.908201512199 + 0.570219149773 + 0.840338947058 + 0.487248598411
6.000000000001  =  0.096738768432  + 0.838905554517 + 0.837179741796 + 0.655925596548 + 0.121227619542
 + 0.393276631434 + 0.529706372738 + 0.627931895727 + 0.857852927706 + 0.827365021028 + 0.213889870533
5.000000000000  =  0.096738768432  + 0.037789824744 + 0.219502575013 + 0.578848374222 + 0.618570311975
 + 0.393356108716 + 0.999687645216 + 0.163539900985 + 0.734447052985 + 0.840338947058 + 0.317180490652
5.000000000001  =  0.096738768432  + 0.093352607179 + 0.600306836676 + 0.914256455483 + 0.618570311975
 + 0.759417445766 + 0.252660056506 + 0.422864494209 + 0.298221673761 + 0.456362751604 + 0.487248598411

25 solutions found in 1.606 seconds, sampling 0.000001% of available space.

最后，它很容易扩展：

N = 1200; a = np.random.random(N)
b = np.random.random()
k = 80; s = nt6.trial(a, b, k)

输出：

...
<  --   snip   --  >
...
37.000000000000  =  0.189587827991   + 0.219870655535 + 0.422462560363 + 0.446529942912 + 0.340513300967
 + 0.272272603670 + 0.701821613150 + 0.016414376458 + 0.228845802410 + 0.071882553217 + 0.966675626054
 + 0.947578041095 + 0.016404068780 + 0.010927217220 + 0.160372498474 + 0.498852167218 + 0.018622555121
 + 0.199963779290 + 0.977205343235 + 0.272323870374 + 0.468492667326 + 0.405511314584 + 0.091160625930
 + 0.243752782720 + 0.563265391730 + 0.938591630157 + 0.053376502849 + 0.176084585660 + 0.212015784524
 + 0.093291552095 + 0.272949310717 + 0.697415829563 + 0.296772790257 + 0.302205095562 + 0.928446954142
 + 0.033615064623 + 0.038778684994 + 0.743281078457 + 0.931343341817 + 0.995992351352 + 0.803282407390
 + 0.714717982763 + 0.002658373156 + 0.366005349525 + 0.569351286490 + 0.515456813437 + 0.193641742784
 + 0.188781686796 + 0.622488518613 + 0.632796984155 + 0.343964602031 + 0.494069912343 + 0.891150139880
 + 0.526788287274 + 0.066698500327 + 0.236622057166 + 0.249176977739 + 0.881250574063 + 0.940333075706
 + 0.936703186575 + 0.400023784940 + 0.875090761246 + 0.485734931256 + 0.281568612107 + 0.493793875212
 + 0.021540268393 + 0.576960812516 + 0.330968114316 + 0.814755318215 + 0.964632238890 + 0.252849647521
 + 0.328316150100 + 0.831418052792 + 0.474425361099 + 0.877461270445 + 0.720632491736 + 0.719074649194
 + 0.698827578293 + 0.378885181918 + 0.661859236288 + 0.169773462717

119 solutions found in 4.039 seconds, sampling 8.21707e-118% of available space.

请注意，该总和中仅有46个数字是计算得出的，其余34个数字是算法事先随机选择的。

- Paul Panzer

有趣的解决方案。这个方法能否被修改以在不同大小的列表中找到不同大小的子集呢？（例如，在624个元素中找到11个） - John Puccino

@JohnPuccino 当然，更大的N也不是问题，因为我们只使用c的子集，所以超出我们随机样本的一切都将被忽略。更大的k也不是问题；如果它变得太大，我们可以取一个大小为l的c的随机子集s'，将其添加到s中，然后解决k-l代替k和s+sum(s')代替s的问题。我会更新帖子。 - Paul Panzer

@JohnPuccino，实际上是k和N的小值使问题变得困难。如果我将k降至5，N为600，则可以找到解决方案，但通常需要几次尝试。在k=4时，它在1000次尝试中找不到任何解决方案。但在这种情况下，可以使用暴力枚举策略来检查是否存在任何解决方案。 - Paul Panzer

哇..一个真正惊人的解决方案。正是我在寻找的..谢谢！ - John Puccino

@JohnPuccino 实际上，我很好奇这个问题来自哪里。是某种比赛或挑战吗？这似乎是一个很好的问题，可以让学生解决，因为有一些解决方案不需要任何专业知识。 - Paul Panzer

对我来说，需要解决在Hackerrank的最新“编程周”比赛中的“几乎整数石头花园”挑战。 - John Puccino

0

这不如我预期的好，但我花了太多时间在这上面，不能不分享一下

我的想法是通过将大小为10的子集分成2个来将问题从O(n^10)降至O(n^5)

首先，计算所有大小为5的子集，然后按它们的模1余数（使得总和在0到1之间）对它们进行排序

然后一个答案包括添加两个大小为5的子集，使得：

这些子集不相交
总和要么是<e，要么是>1-e且<1+e，要么是>2-e，其中e在您的情况下为10^-12

如果您聪明地迭代大小为5的子集，则这3个检查中的每个都非常便宜（实际上，这就是将O(n^10)变为O(n^5)的部分）

所以是的，这个解决方案是O(n^5)。问题在于我的解决方案：

这是用Python编写的，但Python并不是最快的语言
仍然需要计算所有大小为5的组合，“从600个中选择5个”是无法处理的（共有637262850120种组合）

编辑：我只是随机抽取大小为40的大列表的子集，并测试所有组合。如果不起作用，我会再次随机抽取一个新的子集并重复此过程。这可以通过多线程来改进。

在20分钟后找到了step==44的输出结果：

l = [0.06225774829854913, 0.21267040355189515, 0.21954445729288707, 0.21954445729288707, 0.24621125123532117, 0.24621125123532117, 0.36931687685298087, 0.4017542509913792, 0.41421356237309515, 0.41640786499873883, 0.6619037896906015]
>>> sum(l) + 0.529964086141668
3.999999999955324

注意那个跳过前43步的黑客攻击，如果你想进行真正的计算，请将其注释掉。

from math import pow
from itertools import combinations
import itertools
import random
import time

# Constants
random.seed(1)
listLength = 40
halfsize = 5
halfsize2 = 6
x = 0.529964086141668
epsilon = pow(10,-10)

# Define your list here
#myList = [random.random() for i in range(listLength)]
items = [0.9705627484771391, 0.2788205960997061, 0.620499351813308, 0.0, 0.4222051018559565, 0.892443989449804, 0.41640786499873883, 0.0, 0.6491106406735181, 0.36931687685298087, 0.16552506059643868, 0.04159457879229578, 0.0, 0.04159457879229578, 0.16552506059643868, 0.36931687685298087, 0.6491106406735181, 0.0, 0.41640786499873883, 0.892443989449804, 0.4222051018559565, 0.0, 0.620499351813308, 0.2788205960997061, 0.9705627484771391, 0.2788205960997061, 0.556349186104045, 0.866068747318506, 0.21267040355189515, 0.6014705087354439, 0.038404810405298306, 0.5299640861416677, 0.08304597359457233, 0.7046999107196257, 0.4017542509913792, 0.18033988749894903, 0.045361017187261155, 0.0, 0.045361017187261155, 0.18033988749894903, 0.4017542509913792, 0.7046999107196257, 0.08304597359457233, 0.5299640861416677, 0.038404810405298306, 0.6014705087354439, 0.21267040355189515, 0.866068747318506, 0.556349186104045, 0.2788205960997061, 0.620499351813308, 0.866068747318506, 0.142135623730951, 0.45362404707370985, 0.8062484748656971, 0.20655561573370207, 0.6619037896906015, 0.18033988749894903, 0.7703296142690075, 0.4403065089105507, 0.19803902718556898, 0.049875621120889946, 0.0, 0.049875621120889946, 0.19803902718556898, 0.4403065089105507, 0.7703296142690075, 0.18033988749894903, 0.6619037896906015, 0.20655561573370207, 0.8062484748656971, 0.45362404707370985, 0.142135623730951, 0.866068747318506, 0.620499351813308, 0.0, 0.21267040355189515, 0.45362404707370985, 0.7279220613578552, 0.04159457879229578, 0.4017542509913792, 0.8166538263919687, 0.2956301409870008, 0.8488578017961039, 0.4868329805051381, 0.21954445729288707, 0.0553851381374173, 0.0, 0.0553851381374173, 0.21954445729288707, 0.4868329805051381, 0.8488578017961039, 0.2956301409870008, 0.8166538263919687, 0.4017542509913792, 0.04159457879229578, 0.7279220613578552, 0.45362404707370985, 0.21267040355189515, 0.0, 0.4222051018559565, 0.6014705087354439, 0.8062484748656971, 0.04159457879229578, 0.31370849898476116, 0.63014581273465, 0.0, 0.43398113205660316, 0.9442719099991592, 0.5440037453175304, 0.24621125123532117, 0.06225774829854913, 0.0, 0.06225774829854913, 0.24621125123532117, 0.5440037453175304, 0.9442719099991592, 0.43398113205660316, 0.0, 0.63014581273465, 0.31370849898476116, 0.04159457879229578, 0.8062484748656971, 0.6014705087354439, 0.4222051018559565, 0.892443989449804, 0.038404810405298306, 0.20655561573370207, 0.4017542509913792, 0.63014581273465, 0.8994949366116654, 0.21954445729288707, 0.6023252670426267, 0.06225774829854913, 0.6157731058639087, 0.28010988928051805, 0.0710678118654755, 0.0, 0.0710678118654755, 0.28010988928051805, 0.6157731058639087, 0.06225774829854913, 0.6023252670426267, 0.21954445729288707, 0.8994949366116654, 0.63014581273465, 0.4017542509913792, 0.20655561573370207, 0.038404810405298306, 0.892443989449804, 0.41640786499873883, 0.5299640861416677, 0.6619037896906015, 0.8166538263919687, 0.0, 0.21954445729288707, 0.48528137423856954, 0.810249675906654, 0.21110255092797825, 0.7082039324993694, 0.32455532033675905, 0.08276253029821934, 0.0, 0.08276253029821934, 0.32455532033675905, 0.7082039324993694, 0.21110255092797825, 0.810249675906654, 0.48528137423856954, 0.21954445729288707, 0.0, 0.8166538263919687, 0.6619037896906015, 0.5299640861416677, 0.41640786499873883, 0.0, 0.08304597359457233, 0.18033988749894903, 0.2956301409870008, 0.43398113205660316, 0.6023252670426267, 0.810249675906654, 0.0710678118654755, 0.40312423743284853, 0.8309518948453007, 0.38516480713450374, 0.09901951359278449, 0.0, 0.09901951359278449, 0.38516480713450374, 0.8309518948453007, 0.40312423743284853, 0.0710678118654755, 0.810249675906654, 0.6023252670426267, 0.43398113205660316, 0.2956301409870008, 0.18033988749894903, 0.08304597359457233, 0.0, 0.6491106406735181, 0.7046999107196257, 0.7703296142690075, 0.8488578017961039, 0.9442719099991592, 0.06225774829854913, 0.21110255092797825, 0.40312423743284853, 0.6568542494923806, 0.0, 0.4721359549995796, 0.12310562561766059, 0.0, 0.12310562561766059, 0.4721359549995796, 0.0, 0.6568542494923806, 0.40312423743284853, 0.21110255092797825, 0.06225774829854913, 0.9442719099991592, 0.8488578017961039, 0.7703296142690075, 0.7046999107196257, 0.6491106406735181, 0.36931687685298087, 0.4017542509913792, 0.4403065089105507, 0.4868329805051381, 0.5440037453175304, 0.6157731058639087, 0.7082039324993694, 0.8309518948453007, 0.0, 0.24264068711928477, 0.6055512754639891, 0.16227766016837952, 0.0, 0.16227766016837952, 0.6055512754639891, 0.24264068711928477, 0.0, 0.8309518948453007, 0.7082039324993694, 0.6157731058639087, 0.5440037453175304, 0.4868329805051381, 0.4403065089105507, 0.4017542509913792, 0.36931687685298087, 0.16552506059643868, 0.18033988749894903, 0.19803902718556898, 0.21954445729288707, 0.24621125123532117, 0.28010988928051805, 0.32455532033675905, 0.38516480713450374, 0.4721359549995796, 0.6055512754639891, 0.8284271247461903, 0.2360679774997898, 0.0, 0.2360679774997898, 0.8284271247461903, 0.6055512754639891, 0.4721359549995796, 0.38516480713450374, 0.32455532033675905, 0.28010988928051805, 0.24621125123532117, 0.21954445729288707, 0.19803902718556898, 0.18033988749894903, 0.16552506059643868, 0.04159457879229578, 0.045361017187261155, 0.049875621120889946, 0.0553851381374173, 0.06225774829854913, 0.0710678118654755, 0.08276253029821934, 0.09901951359278449, 0.12310562561766059, 0.16227766016837952, 0.2360679774997898, 0.41421356237309515, 0.0, 0.41421356237309515, 0.2360679774997898, 0.16227766016837952, 0.12310562561766059, 0.09901951359278449, 0.08276253029821934, 0.0710678118654755, 0.06225774829854913, 0.0553851381374173, 0.049875621120889946, 0.045361017187261155, 0.04159457879229578, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.04159457879229578, 0.045361017187261155, 0.049875621120889946, 0.0553851381374173, 0.06225774829854913, 0.0710678118654755, 0.08276253029821934, 0.09901951359278449, 0.12310562561766059, 0.16227766016837952, 0.2360679774997898, 0.41421356237309515, 0.0, 0.41421356237309515, 0.2360679774997898, 0.16227766016837952, 0.12310562561766059, 0.09901951359278449, 0.08276253029821934, 0.0710678118654755, 0.06225774829854913, 0.0553851381374173, 0.049875621120889946, 0.045361017187261155, 0.04159457879229578, 0.16552506059643868, 0.18033988749894903, 0.19803902718556898, 0.21954445729288707, 0.24621125123532117, 0.28010988928051805, 0.32455532033675905, 0.38516480713450374, 0.4721359549995796, 0.6055512754639891, 0.8284271247461903, 0.2360679774997898, 0.0, 0.2360679774997898, 0.8284271247461903, 0.6055512754639891, 0.4721359549995796, 0.38516480713450374, 0.32455532033675905, 0.28010988928051805, 0.24621125123532117, 0.21954445729288707, 0.19803902718556898, 0.18033988749894903, 0.16552506059643868, 0.36931687685298087, 0.4017542509913792, 0.4403065089105507, 0.4868329805051381, 0.5440037453175304, 0.6157731058639087, 0.7082039324993694, 0.8309518948453007, 0.0, 0.24264068711928477, 0.6055512754639891, 0.16227766016837952, 0.0, 0.16227766016837952, 0.6055512754639891, 0.24264068711928477, 0.0, 0.8309518948453007, 0.7082039324993694, 0.6157731058639087, 0.5440037453175304, 0.4868329805051381, 0.4403065089105507, 0.4017542509913792, 0.36931687685298087, 0.6491106406735181, 0.7046999107196257, 0.7703296142690075, 0.8488578017961039, 0.9442719099991592, 0.06225774829854913, 0.21110255092797825, 0.40312423743284853, 0.6568542494923806, 0.0, 0.4721359549995796, 0.12310562561766059, 0.0, 0.12310562561766059, 0.4721359549995796, 0.0, 0.6568542494923806, 0.40312423743284853, 0.21110255092797825, 0.06225774829854913, 0.9442719099991592, 0.8488578017961039, 0.7703296142690075, 0.7046999107196257, 0.6491106406735181, 0.0, 0.08304597359457233, 0.18033988749894903, 0.2956301409870008, 0.43398113205660316, 0.6023252670426267, 0.810249675906654, 0.0710678118654755, 0.40312423743284853, 0.8309518948453007, 0.38516480713450374, 0.09901951359278449, 0.0, 0.09901951359278449, 0.38516480713450374, 0.8309518948453007, 0.40312423743284853, 0.0710678118654755, 0.810249675906654, 0.6023252670426267, 0.43398113205660316, 0.2956301409870008, 0.18033988749894903, 0.08304597359457233, 0.0, 0.41640786499873883, 0.5299640861416677, 0.6619037896906015, 0.8166538263919687, 0.0, 0.21954445729288707, 0.48528137423856954, 0.810249675906654, 0.21110255092797825, 0.7082039324993694, 0.32455532033675905, 0.08276253029821934, 0.0, 0.08276253029821934, 0.32455532033675905, 0.7082039324993694, 0.21110255092797825, 0.810249675906654, 0.48528137423856954, 0.21954445729288707, 0.0, 0.8166538263919687, 0.6619037896906015, 0.41640786499873883, 0.892443989449804, 0.038404810405298306, 0.20655561573370207, 0.4017542509913792, 0.63014581273465, 0.8994949366116654, 0.21954445729288707, 0.6023252670426267, 0.06225774829854913, 0.6157731058639087, 0.28010988928051805, 0.0710678118654755, 0.0, 0.0710678118654755, 0.28010988928051805, 0.6157731058639087, 0.06225774829854913, 0.6023252670426267, 0.21954445729288707, 0.8994949366116654, 0.63014581273465, 0.4017542509913792, 0.20655561573370207, 0.038404810405298306, 0.892443989449804, 0.4222051018559565, 0.6014705087354439, 0.8062484748656971, 0.04159457879229578, 0.31370849898476116, 0.63014581273465, 0.0, 0.43398113205660316, 0.9442719099991592, 0.5440037453175304, 0.24621125123532117, 0.06225774829854913, 0.0, 0.06225774829854913, 0.24621125123532117, 0.5440037453175304, 0.9442719099991592, 0.43398113205660316, 0.0, 0.63014581273465, 0.31370849898476116, 0.04159457879229578, 0.8062484748656971, 0.6014705087354439, 0.4222051018559565, 0.0, 0.21267040355189515, 0.45362404707370985, 0.7279220613578552, 0.04159457879229578, 0.4017542509913792, 0.8166538263919687, 0.2956301409870008, 0.8488578017961039, 0.4868329805051381, 0.21954445729288707, 0.0553851381374173, 0.0, 0.0553851381374173, 0.21954445729288707, 0.4868329805051381, 0.8488578017961039, 0.2956301409870008, 0.8166538263919687, 0.4017542509913792, 0.04159457879229578, 0.7279220613578552, 0.45362404707370985, 0.21267040355189515, 0.0, 0.620499351813308, 0.866068747318506, 0.142135623730951, 0.45362404707370985, 0.8062484748656971, 0.20655561573370207, 0.6619037896906015, 0.18033988749894903, 0.7703296142690075, 0.4403065089105507, 0.19803902718556898, 0.049875621120889946, 0.0, 0.049875621120889946, 0.19803902718556898, 0.4403065089105507, 0.7703296142690075, 0.18033988749894903, 0.6619037896906015, 0.20655561573370207, 0.8062484748656971, 0.45362404707370985, 0.142135623730951, 0.866068747318506, 0.620499351813308, 0.2788205960997061, 0.556349186104045, 0.866068747318506, 0.21267040355189515, 0.6014705087354439, 0.038404810405298306, 0.5299640861416677, 0.08304597359457233, 0.7046999107196257, 0.4017542509913792, 0.18033988749894903, 0.045361017187261155, 0.0, 0.045361017187261155, 0.18033988749894903, 0.4017542509913792, 0.7046999107196257, 0.08304597359457233, 0.5299640861416677, 0.038404810405298306, 0.6014705087354439, 0.21267040355189515, 0.866068747318506, 0.556349186104045, 0.2788205960997061, 0.9705627484771391, 0.2788205960997061, 0.620499351813308, 0.0, 0.4222051018559565, 0.892443989449804, 0.41640786499873883, 0.0, 0.6491106406735181, 0.36931687685298087, 0.16552506059643868, 0.04159457879229578, 0.0, 0.04159457879229578, 0.16552506059643868, 0.36931687685298087, 0.6491106406735181, 0.0, 0.41640786499873883, 0.892443989449804, 0.4222051018559565, 0.0, 0.620499351813308, 0.2788205960997061, 0.9705627484771391]
items = sorted(items)
#print(len(items))
#print(items)

itemSet = sorted(list(set(items)))
#print(len(itemSet))
#print(itemSet)
#print(myList)

#Utility functions
#s is a set of indices
def mySum(s):
  return (sum([myList[i] for i in s]))%1

def mySum2(s):
  return (sum([myList[i] for i in s]) + x)%1


start = time.time()


for step in range(1, 1000000):

    myList = random.sample(items,  listLength)
    # HACK
    if(step<44):
        continue

    print("Step %s"%(step))
    myList = sorted(myList)

    listHalfIndices = [i for i in combinations(range(len(myList)),halfsize)]
    listHalfIndices1 = sorted(listHalfIndices, key = mySum)
    #print(listHalfIndices)
    #print([mySum(s) for s in listHalfIndices])

    listHalfIndices2 = [i for i in combinations(range(len(myList)),halfsize2)]
    listHalfIndices2 = sorted(listHalfIndices2, key = mySum2)
    #print(listHalfIndices2)
    #print([mySum2(s) for s in listHalfIndices2])
    """
    # SKIP THIS as I heuristically noted that it was pretty useless
    # First answer if the sum of the first and second list is smaller than epsilon
    print("ANSWER TYPE 1")
    #print([mySum(s) for s in listHalfIndices1[0:10]])
    #print([mySum2(s) for s in listHalfIndices2[0:10]])


    listLowIndices1 = [s for s in listHalfIndices1 if mySum(s) <= epsilon]
    #print(listLowIndices1)
    #print([mySum(s) for s in listLowIndices1])

    listLowIndices2 = [s for s in listHalfIndices2 if mySum2(s) <= epsilon]
    #print(listLowIndices2)
    #print([mySum2(s) for s in listLowIndices2])

    combinationOfIndices1 = [list(set(sum(i, ()))) for i in itertools.chain(itertools.product(listLowIndices1, listLowIndices2))]
    #print(combinationOfIndices1)
    #print([mySum2(s) for s in combinationOfIndices1])

    answer1 = [i for i in combinationOfIndices1 if len(i) == (2*halfsize) and mySum2(i)<=epsilon]
    if(len(answer1) > 0):
        print (answer1)
        print([mySum2(s) for s in answer1])
        break

    # Second answer if the sum of the first and second list is larger than 2-epsilon
    print("ANSWER TYPE 2")
    #print([mySum(s) for s in listHalfIndices1[-10:-1]])
    #print([mySum2(s) for s in listHalfIndices2[-10:-1]])

    listHighIndices1 = [s for s in listHalfIndices1 if mySum(s) >= 1-epsilon]
    #print(listHighIndices1)

    listHighIndices2 = [s for s in listHalfIndices2 if mySum2(s) >= 1-epsilon]
    #print(listHighIndices2)

    combinationOfIndices2 = [list(set(sum(i, ()))) for i in itertools.chain(itertools.product(listHighIndices1, listHighIndices2))]
    #print(combinationOfIndices2)
    #print([mySum2(s) for s in combinationOfIndices2])

    answer2 = [i for i in combinationOfIndices2 if len(i) == (2*halfsize) and mySum2(i)>=1-epsilon]
    if(len(answer2) > 0):
        print (answer2)
        print([mySum2(s) for s in answer2])
        break
    """
    # Third answer if the sum of the first and second list is between 1-epsilon and 1+epsilon
    #print("ANSWER TYPE 3")
    i = 0
    j = len(listHalfIndices2) - 1
    answer3 = None
    print("Answer of type 3 will explore at most %s combinations "%(2*len(listHalfIndices2)))
    for k in range(2*len(listHalfIndices2)): 
        if(k%1000000 == 0 and k>0):
                print(k)
        setOfIndices = list(set(listHalfIndices1[i] + listHalfIndices2[j]))
        #print(setOfIndices)

        currentSum = mySum(listHalfIndices1[i]) + mySum2(listHalfIndices2[j])
        #print(currentSum)
        if(currentSum < 1-epsilon):
            i = i+1
            if(i>=len(listHalfIndices1)):
                break
            #print("i++")
        else:
            j = j-1
            if(j<0):
              break
            #print("j--")
        if(len(setOfIndices) < (halfsize+halfsize2)):
            #print("skipping")
            continue

        if(currentSum >= 1-epsilon and currentSum <= 1+epsilon):
            print("Found smart combination with sum : s=%s"%(currentSum))
            print(sorted([myList[i] for i in setOfIndices]))
            answer3 = setOfIndices
            break

    if answer3 is not None:
        break

end = time.time()
print("Time elapsed %s"%(end-start))

- B. Decoster

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tristan · Accepted Answer

这个问题可以被表述为一个数学规划问题，这使得我们能够使用专门的算法来解决它，比如单纯形算法和分支定界算法。在大多数情况下，使用分支定界算法只需要查看搜索树的一小部分就可以找到最优解。

在Python中，有许多用于制定和解决混合整数规划的库。我认为CyLP和PuLP是其中知名的免费库之一。

easy_install pulp

如果您可以轻松安装，PuLP带有一个免费的整数问题求解器设置，因此我建议使用PuLP，如果它适用于您的问题。

这是一个针对PuLP的问题实现：

from pulp import *

items = [1.000123,2.192,3.2143124,1.00041,2.0043,3.5]
x = 0.5
tol = 0.001
numstouse = 3

delta = pulp.LpVariable.dicts('listitems', range(len(items)), lowBound = 0, upBound = 1, cat = pulp.LpInteger)
s = pulp.LpVariable('value', lowBound = 0, cat = pulp.LpInteger)
r = pulp.LpVariable('deviation', lowBound = -tol, upBound=tol)

# Model formulation
prob = LpProblem("Sum Problem", LpMinimize)

# Constraints
prob += lpSum([delta[i] * items[i] for i in range(len(items))]) + x + r == s
prob += lpSum([delta[i] for i in range(len(items))]) == numstouse
prob.solve()
print("Found combination: s={} for {}".format(s.value(), tuple(items[i] for i in range(len(items)) if delta[i].value() == 1)))
if LpStatus[prob.status] == "Optimal":
    for i in delta.keys():
        if delta[i].value() == 1:
            print("List item {} is used in the sum with value {}.".format(i, items[i]))
else:
    print("The problem seems to be infeasible.")

需要注意的是，虽然PuLP默认免费求解器最终会解决您的问题，但商业求解器比免费求解器快很多倍。随着问题规模的增大，免费求解器可能比商业求解器慢得多。