【算法】Bortfeldt关于解决RPP问题的论文中提到的生成候选框宽的WV3方法

问题

首先，确定合理宽度值的区间\([w_{min},w_{max}]\) 。其中\(w_{min}\)设置为所有矩形中较小尺寸的最大值。\(w_{max}\)设置为\([area(R)^{1/2}*α]\)，其中area(R)代表所有矩形的总面积，α是不大于\(a\)的最大整数。我们可以假设\(w_C≤l_C\)，因为此处不存在方向约束。对于100%的最佳密度，考虑不大于 \([area(R)^{1/2}]\)的宽度值就足够了。由于最优解的密度通常较低，因此通过参数\(α>1\)为\(w_{max}\)选择相对较大的值。对于每个宽度\(w_C\in[w_{min},w_{max}]\)，通过算法SPA求解相应的2D-SPP实例\((w_C,R)\)，并将最佳解作为初始RPAMP解。

宽度值\(w_C\)的宽度组合被定义为一组矩形尺寸（\(l_i\)或\(w_i\)的和，\(i\in\{1,...,n\}\)）。宽度\(w_C\)的频率\(nc(w_C)wC\)由值\(w_C\)的所有宽度组合的数量给出，即其中矩形尺寸之和等于\(w_C\)的所有宽度组合的数量。每个组合的维数由参数\(maxitems\)给出。

解决方法

论文描述的方法

在这里处理的组合问题可以称为区间子集和问题（Interval Subset Sum Problem）：

给出\(n(n>1)\)个正整数\(w_i\)，一个区间\([w_{min},w_{max}]\)\((w_{min}\)和\(w_{max}\)也是正整数)以及一个正整数\(p_{max}\)。每一个p元组\((w_{i_1},w_{i_2},...,w_{i_p})\)被称为一个选择，其中\(i_k<i_{(k+1)}(k=1,...,p-1;1\leq i_1,i_p\leq n)\)，\(p\)被称为它的长度。如果一个选择\(s=(w_{i_1},w_{i_2},...,w_{i_p})\)存在\(w_{i_1}+w_{i_2}+...+w_{i_p}=w\)，则称该选择\(s\)的和为\(w\)。对于每个\(w\in [w_{min},w_{max}]\)和每个长度\(p\in [1,p_{max}]\)，我们必须确定长度\(p\)和\(w\)的所有的不同选择的数量\(N^p(w)\)，要求\(w\in [w_{min},w_{max}]\)，\(p\leq p_{max}\)。我们可以假设\(w_i\leq w_{max}\)以及\(w_1+w_2+...+w_n\geq w_{min}(i=1,...,n)\)。

为了求解ISSP，提出了一种基于假设\(w_i<w_{i+1}(i=1,...,n-1)\)的动态规划的过程。我们把整个过程约束在所有整数\(w_i\)都不相等的情况下。

设\(N^{p,i}(w)\)表示所有长度为\(p\)和为\(w\)的选择\(s\)，附加属性为\(s\)的最后一个值为\(w_i(1\leq i\leq n,1\leq w \leq w_{max},1 \leq p \leq p_{max})\)。如果\(w\leq 0\)则\(N^{p,i}(w)\)为0。注意，如果\(i<p\)则\(N^{p,i}(w)=0\)。则长度\(p=1\)的选择方程为： \[ N^{1,i}(w)=1,仅当w=w_i,i\in\{1,...,n\},w\in [1,w_{max}]\tag{1} \] 每个和为\(w\)、长度为\(p+1\)、最后一个值为\(w_i\)的选择\(s'\)都可以从一个和为\(w-w_i\)、长度为\(p\)的选择\(s\)得到。\(s\)是通过\(s'\)删除最后一个值\(w_i\)得到的。因此我们有以下递归： \[ N^{p+1,i}(w)=\sum_{j<i}N^{p,j}(w-w_i),i\in\{1,...,n\}\\ p\in\{1,...,p_{max}-1\},w\in[1,w_{max}].\tag{2} \] 通过关系（1）和（2）我们能够计算出所有的数字\(N^{p,i}(w)(1\leq i\leq n,w_{min}\leq w\leq w_{max},1\leq p\leq p_{max} )\)。最后可以得出等式\(N^p(w)=\sum_{i-1}^n N^{p,i}(w),(w_{min}\leq w\leq w_{max},1\leq p\leq p_{max} )\)以及\(N(w)=\sum_{p-1}^{p_{max}}N^p(w),(w_{min}\leq w\leq w_{max})\)。

递归（2）的计算构成了这个过程中最耗时的部分。很容易看出，这种计算的最坏情况复杂度为\(O(w_{max}n^2)\)。因此，ISSP的动态规划过程具有伪多项式复杂度。这个过程可以很容易地扩展为这样一种方式：输出正好由p个值求和或最多p个值求和得到的所有值在区间\([w_{min},w_{max}]\)内的和\(w\)的不同选择。

人话版方法

------上面是论文里面提出的复杂公式，下面是在知乎上看到的简略版---------

对于某个给定值M，如何从某个给定的正整数集合S中找个一个子集合s，使得该子集和为给定值M。如M=7，S={1,3,4,5}，则s={3,4}.

对于\(S={a_1,a_2,...,a_n}\)，每个元素只有取与不取两种情况，再考虑它们的和是否等于M，但是这样的情况共有\(2^n\)种，这种算法的效率显然是不行的。

换条思路，令subset(i,j)表示S中前i个元素的子集和等于j的情况，则

若S[i] > j，则S[i]不在子集s中。
若S[i] <= j, 则有以下两种情况：一种情况是S[i]不在子集s中，则subset(i, j) = subset(i-1, j); 一种情况是S[i]在子集s中，则subset(i, j)= subset(i-1, j-S[i]).

这样就有了这个问题的子结构问题，因此，只需要确定初始情况即可：

对于i=0,1,2,…,n,有subset(i, 0)=True, 对于j=1,2,…,M, 有subset(0, j)=False.

因此，利用动态规划法，就能得到(n+1)*(M+1)的真值表了，而答案就是subset(n, M). 算法有了，Python代码自然也有了：

import numpy as np
# A Dynamic Programming solution for subset sum problem
# Returns true if there is a subset of set with sum equal to given sum
def isSubsetSum(S, n, M):
    # The value of subset[i, j] will be
    # true if there is a subset of
    # set[0..j-1] with sum equal to i
    subset = np.array([[True]*(M+1)]*(n+1))
    # If sum is 0, then answer is true
    for i in range(0, n+1):
        subset[i, 0] = True
    # If sum is not 0 and set is empty,
    # then answer is false
    for i in range(1, M+1):
        subset[0, i] = False
    # Fill the subset table in bottom-up manner
    for i in range(1, n+1):
        for j in range(1, M+1):
            if j < S[i-1]:
                subset[i, j] = subset[i-1, j]
            else:
                subset[i, j] = subset[i-1, j] or subset[i-1, j-S[i-1]]
    # print the True-False table
    for i in range(0, n+1):
        for j in range(0, M+1):
            print('%-6s'%subset[i][j], end="  ")
        print(" ")
    if subset[n, M]:
        print("Found a subset with given sum")
    else:
        print("No subset with given sum")
# test
st = [1, 3, 4, 5]
n = len(st)
sm = 7
isSubsetSum(st, n, sm)

输出结果如下：

True False False False False False False False True True False False False False False False True True False True True False False False True True False True True True False True True True False True True True True True Found a subset with given sum

那么，怎样求解子集s中的元素呢？也许可以用回溯法（backtracing）找出s中的元素。可以从输出的真值表入手：

对于subset(i, j) = subset(i-1, j)=True,则元素S[i]不在子集s中。对于subset(i,j)=True而subset(i-1, j)=False，则元素S[i]必定在子集s中，此时subset(i-1, j-S[i])=True，这样就能通过递归法找到s中的元素了。对于这个问题，只要从subset(n, M)开始即可。

import numpy as np
# A Dynamic Programming solution for subset sum problem
# Returns true if there is a subset of set with sum equal to given sum
def isSubsetSum(S, n, M):
    # The value of subset[i, j] will be
    # true if there is a subset of
    # set[0..j-1] with sum equal to i
    subset = np.array([[True]*(M+1)]*(n+1))
    # If sum is 0, then answer is true
    for i in range(0, n+1):
        subset[i, 0] = True
    # If sum is not 0 and set is empty,
    # then answer is false
    for i in range(1, M+1):
        subset[0, i] = False
    # Fill the subset table in bottom-up manner
    for i in range(1, n+1):
        for j in range(1, M+1):
            if j < S[i-1]:
                subset[i, j] = subset[i-1, j]
            else:
                subset[i, j] = subset[i-1, j] or subset[i-1, j-S[i-1]]
    # print the True-False table
    for i in range(0, n+1):
        for j in range(0, M+1):
            print('%-6s'%subset[i][j], end="  ")
        print(" ")
    if subset[n, M]:
        print("Found a subset with given sum")
        sol = []
        # using backtracing to find the solution
        i = n
        while i >= 0:
            if subset[i, M] and not subset[i-1, M]:
                sol.append(S[i-1])
                M -= st[i-1]
            if M == 0:
                break
            i -= 1
        print('The solution is %s.' % sol)
    else:
        print("No subset with given sum")
# test
st = [1, 3, 4, 5]
n = len(st)
sm = 7
isSubsetSum(st, n, sm)

输出结果如下：

True False False False False False False False True True False False False False False False True True False True True False False False True True False True True True False True True True False True True True True True Found a subset with given sum The solution is [4, 3].