最大分区

Question

给出整数n和2个实数序列{a_1，...，a_n}和{b_1，...，b_n} ，对于所有i，<< a_i，b_i> 0。对于给定的固定m <n，让{P_1，...，P_m}是集合{1，...，n]的分区>}，如P_1 U ... U P_n = {1，...，n}，其中P_i的成对不相交（空交集）。我希望找到一个大小为[[m的分区，以使表达式最大化

集合的分区数为

n

选择

m

，用蛮力做得太大了。有没有更好的迭代解决方案？为了深入了解此问题，以下内容通过蛮力解决。对于实际的大小问题（n〜1e6，

k

〜20），它原样不可用，但很容易分发。

 import numpy as np
 from itertools import permutations

 rng = np.random.RandomState(55)

 def knuth_partition(ns, m):
     def visit(n, a):
         ps = [[] for i in range(m)]
         for j in range(n):
             ps[a[j + 1]].append(ns[j])
         return ps

     def f(mu, nu, sigma, n, a):
         if mu == 2:
             yield visit(n, a)
         else:
             for v in f(mu - 1, nu - 1, (mu + sigma) % 2, n, a):
                 yield v
         if nu == mu + 1:
             a[mu] = mu - 1
             yield visit(n, a)
             while a[nu] > 0:
                 a[nu] = a[nu] - 1
                 yield visit(n, a)
         elif nu > mu + 1:
             if (mu + sigma) % 2 == 1:
                 a[nu - 1] = mu - 1
             else:
                 a[mu] = mu - 1
             if (a[nu] + sigma) % 2 == 1:
                 for v in b(mu, nu - 1, 0, n, a):
                     yield v
             else:
                 for v in f(mu, nu - 1, 0, n, a):
                     yield v
             while a[nu] > 0:
                 a[nu] = a[nu] - 1
                 if (a[nu] + sigma) % 2 == 1:
                     for v in b(mu, nu - 1, 0, n, a):
                         yield v
                 else:
                     for v in f(mu, nu - 1, 0, n, a):
                         yield v

     def b(mu, nu, sigma, n, a):
         if nu == mu + 1:
             while a[nu] < mu - 1:
                 yield visit(n, a)
                 a[nu] = a[nu] + 1
             yield visit(n, a)
             a[mu] = 0
         elif nu > mu + 1:
             if (a[nu] + sigma) % 2 == 1:
                 for v in f(mu, nu - 1, 0, n, a):
                     yield v
             else:
                 for v in b(mu, nu - 1, 0, n, a):
                     yield v
             while a[nu] < mu - 1:
                 a[nu] = a[nu] + 1
                 if (a[nu] + sigma) % 2 == 1:
                     for v in f(mu, nu - 1, 0, n, a):
                         yield v
                 else:
                     for v in b(mu, nu - 1, 0, n, a):
                         yield v
             if (mu + sigma) % 2 == 1:
                 a[nu - 1] = 0
             else:
                 a[mu] = 0
         if mu == 2:
             yield visit(n, a)
         else:
             for v in b(mu - 1, nu - 1, (mu + sigma) % 2, n, a):
                 yield v

     n = len(ns)
     a = [0] * (n + 1)
     for j in range(1, m + 1):
         a[n - m + j] = j - 1
     return f(m, n, 0, n, a)

 def Bell_n_k(n, k):
     ''' Number of partitions of {1,...,n} into
         k subsets, a restricted Bell number
     '''
     if (n == 0 or k == 0 or k > n): 
         return 0
     if (k == 1 or k == n): 
         return 1

     return (k * Bell_n_k(n - 1, k) + 
                 Bell_n_k(n - 1, k - 1)) 

 NUM_POINTS = 12
 PARTITION_SIZE = 4
 INT_LIST= range(0, NUM_POINTS)
 REPORT_EACH = 10000


 a = rng.uniform(low=0.0, high=10.0, size=NUM_POINTS)
 b = rng.uniform(low=0.0, high=10.0, size=NUM_POINTS)

 max_sum = float('-inf')
 num_partitions = Bell_n_k(NUM_POINTS, PARTITION_SIZE)
 for ind, part in enumerate(knuth_partition(INT_LIST, PARTITION_SIZE)):
     val = 0
     for p in part: 
         val += sum(a[p])**2/sum(b[p])
     if val > max_sum:
         max_sum = val
         argmax = (ind, part)
     if not ind%REPORT_EACH:
         print('Percent complete: {:.{prec}f}'.format(100*ind/num_partitions, prec=2))

给定整数n和2个实数序列{a_1，...，a_n}和{b_1，...，b_n}，对于所有i，a_i，b_i> 0。对于给定的固定m

我试图用示例输入简单地重新表述问题，让我知道是否错过了任何内容。
A = [1、3、2、1、4]B = [2，1，5，3，1]n =长度（A）=长度（B）= 5
我们有两个带有正整数的列表。
我们需要找到一组索引S（N的子集= {1,2,3，.. n}），我们假设它是{2,3,5}。现在，我们得到一个新集合S'= N-S = {1，4}
对于S和S'，需要将（sum（A [S]]）^ 2 /（sum（B [S']）））最大化。
正如您所说，近似解也将起作用。我们可以使用的一种启发式方法是，我们需要选择这样的S，以使A list的值较高而B list的值为低。
当我们对A的子集求和的平方时，让我们对A进行排序，然后选择一个子列表，以便获得最高分。
import numpy as np

A = np.array([1, 2, 3, 4, 1, 2, 3])
B = np.array([3, 3, 1, 2, 1, 3, 1])

sorted_idx = sorted(range(len(A)), key=lambda k: A[k]) # also other sorting strategy can be used, A[k]/B[k]

A_p = A[sorted_idx]
B_p = B[sorted_idx]

max_s = 0
part_ans = -1

for i in range(len(A_p)):
  cur_s = (sum(A_p[:i])**2)/sum(B_p[i:])
  if cur_s >= max_s:
    print(cur_s)
    max_s = cur_s
    part_ans = i

print(f'The partitions are: {sorted_idx[:i]} and {sorted_idx[i:]}')

Answer 1