背包

(Updated: )

背包问题（Knapsack Problem）

背包问题是个著名的NP-问题，通常出现于让我们求子集问题上面

低密度子集问题（Low-density Subset Sum Problems）

定义

给予了一系列正整数a1, a2, a3......an(权重)，以及一个整数s，然后找到一系列e1, e2, e3......en(ei ∈ {0, 1})满足式子 集合a1, a2, a3......an的密度计算公式如下 在满足d < 0.9408的情况下时，我们构造格如下格来解决这个问题 所以我们的预期是通过LLL算法对上述格进行规约得到这个短向量，但是这个方法在密度比较高的时候会失效，所以又使得我们可以通过将子集和问题转换为SVP从而在多项式时间内求解这个问题，CJLOSS算法中构造的格为： 其中并且为整数并且显然这条短向量的模为,我们很容易可以通过LLL算法求解出这条短向量（这个短向量一般是规约后的格的第一个向量，且前个元素往往为

背包问题通解格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
M =[]
S =
 
ge = Matrix(ZZ,len(M)+1)
for i in range(len(M)):
    ge[i,i] = 2
    ge[i,-1] = M[i]
    ge[-1,i] = 1
ge[-1,-1] = S
Ge = ge.LLL()[0]
print(Ge)
 
m = ""
for i in Ge[:-1]:
    m += str(((i+1)//2^^1))
print(m)
print(int(m,2))

CJLOSS算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#sage
def CJLOSS(A, s):
    n = len(A)
    N = ceil(sqrt(n))
    L = matrix(QQ, n + 1)
    for i in range(n):
        L[i, i] = 1
        L[n, i] = 1/2
        L[i, n] = N * A[i]
    L[n, n] = N * s
    res = L.LLL()
    for v in res:
        if all(x in [-1/2, 1/2] for x in v[:-1]):
            out = [1/2 - a for a in v[:-1]]
            return out