0%

01背包问题四类解法

Posted on Edited on In

问题描述

有$n$个物品要放入背包，第$i$个物品的重量是$w_i$ ,价值是$v_i$ 背包的总容量为$c$ , 要选择一部分商品放入背包，使得他们总价值最大。用数学语言描述就是：

在满足$\sum_i^n w_ix_i \leq c$ 的情况下求 $max(\sum_i^n vix_i)$ 其中$x_i \in {0,1}$

背包问题可以看做是一个子集合问题。

使用的benchmark来自https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html

暴力解法

算法复杂度为$O(2^n)$

每种商品都可以选择放或者不放，共用2种情况，n个物品，所以总共有$2^n$ 次可能，暴力遍历所有可能，如果容量没有超过背包则计算其总价值。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#!/usr/bin/env python3

n = 10
c = 165

with open("value_{}_{}".format(n, c)) as f:
    values_ = f.read().split("\n")

with open("weight_{}_{}".format(n, c)) as f:
    weights_ = f.read().split("\n")

values = list(map(int, values_))
weights = list(map(int, weights_))

maxValue = 0
target = None
for i in range(2**n):
    index = [(i&2**j)>>j for j in range(n)]
    tmpWeight = sum([i*j for i,j in zip(weights, index)])
    if tmpWeight > c:
        continue
    tmpValue = sum([i*j for i,j in zip(values, index)])
    if tmpValue > maxValue:
        target = index[:]
        maxValue = tmpValue

print(maxValue, target)

动态规划

算法复杂度为$O(nC)$

$F(i, c)$

$F(i,c)$ 表示从前$i$物品选一些物品装入到容量为$c$ 的包内物品最大价值

那么递推公式就为, 就是考虑第i个物品是否放进去，如果放进去则是（潜在的条件是$w_i\leq c$）$F(i-1, c-w_i)+v_i$ 不放的话就是$F(i-1), c$

递归实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#!/usr/bin/env python3
import sys

# n = 24
# c = 6404180
# res = 13549094
n = 10
c = 165

with open("value_{}_{}".format(n, c)) as f:
    values = f.read().split("\n")

with open("weight_{}_{}".format(n, c)) as f:
    weights = f.read().split("\n")

data = [(int(weight),int(value)) for weight, value in zip(weights, values)]

#p(c) = max(p(c-wi)+vi)
#f[i][c] 表示从前i件中挑选出使得容量为c的背包value最大
#f[i][c] = max(f[i][c-wi]+vi, f[i-1][c])
#复杂度为(CN)
dp = {}
def dynaymic_program(i, c):
    # print(i,c)
    if i == 0:
        if data[i][0] <= c:
            dp[(i,c)] = data[i][1]
            return data[i][1]
        else:
            dp[(i,c)] = 0
            return 0
    
    if (i,c) in dp:
        return dp[(i,c)]
    else:
        r1 = dynaymic_program(i-1, c)
        r2 = 0
        if c - data[i][0] >= 0:
            r2 = dynaymic_program(i-1, c - data[i][0]) + data[i][1]
        # if r1 < r2:
        #     choice.append(data[i])

        dp[(i,c)] = max(r1, r2)
        return max(r1, r2)

def get_Solution():
    choice = [0]*n
    tmpc = c
    index = n-1
    while index > 0:
        if tmpc - data[index][0] < 0:
            break
        if dp[(index,tmpc)] > dp[(index-1, tmpc)]:
            choice[index] = 1
            tmpc = tmpc-data[index][0]
        
        index = index - 1
    if tmpc == data[0][0]:
        choice[0] = 1
    return choice

if __name__ == "__main__":
    ret = dynaymic_program(n-1, c)
    print(ret)
    choice = get_Solution()
    print(choice)
    # print(dp)

$F(i,v)$

算法复杂度为$n^2V$ 其中V为$max(v_i)$

$F(i,v)$ 表示前$i$个物品中刚好能选出一部分物品其总价值$v$, 所需要的最小容量。如果第i个物品被选中(潜在的条件是$v_i < v$)

$F(i,v) = F(i-1, v-v_i)+w_i$ 如果不放则递推为

$F(i,v) = F(i-1,v)$ 两者选最小值

如果不能从前i个里面选出部分物品是其总价值刚好是v，则返回无穷大

迭代实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#!/usr/bin/env python3
import sys

# n = 24
# c = 6404180
# res = 13549094
n = 10
c = 165
n = 15
c = 750


with open("value_15_750") as f:
    values_ = f.read().split("\n")

with open("weight_15_750") as f:
    weights_ = f.read().split("\n")

values = list(map(int, values_))
weights = list(map(int, weights_))
data = [(weight,value) for weight, value in zip(weights, values)]

#f(i,v) 表示从前i件中挑选出使得价值为v,并且是size最小, 如果找不到就无穷大
#f(i,v) 表示
#V = max(v)
#复杂度为(n**2 * V)

def get_Solution(j):
    choice = [0]*n
    for i in range(n-1, 0, -1):
        if dp[i][j] != dp[i-1][j]:
            choice[i] = 1
            j = j - values[i]
        if j == values[0]:
            choice[0] = 1
    return choice

if __name__ == "__main__":
    V = max(values)
    ret = []
    target = 0
    index = None
    dp = [[sys.maxsize]*(n*V) for __ in range(n)]
    dp[0][values[0]] = weights[0]
    # print(dp)
    for i in range(1,n):
        for j in range(n*V):
            if j - values[i] >= 0:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-values[i]]+weights[i])
            else:
                dp[i][j] = dp[i-1][j]
            
            if dp[i][j] <= c:
                target = j
                index = (i,j)
    print(target)
    choice = get_Solution(target)
    print(choice)

近似算法

近似算法是根据上面的$F(i,v)$ 改进的。

背包问题的FPTAS，能够在n和$\frac{1}{\epsilon}$ 的多项式时间得到一个结果至少为$(1-\epsilon)*OPT$

算法复杂度为$O(n^2\lfloor\frac{n}{\epsilon}\rfloor)$

算法的核心思想是将$v_i$ 进行放缩

  1. 给定$\epsilon > 0$ 设$K = \frac{\epsilon V}{n}$ ， $V=max(v_i)$
  2. 计算$v_i^{‘} = \lfloor \frac{v_i}{K}\rfloor$
  3. 然后根据新的$v_i’$ 利用$F(i,v)$ 计算背包问题，输出解

下面给出证明

因为$v_i^{‘} = \lfloor \frac{v_i}{K}\rfloor$

所以

所以

所以$xi \in O$ ， $O$ 为原始背包问题的最优解

所以

对于放缩后的背包问题的最优解为$S’$ 有

即

有因为$V \leq OPT$ 所以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#!/usr/bin/env python3
import sys 
import math
# n = 24
# c = 6404180
# res = 13549094
n = 10
c = 165
n = 15
c = 750
n = 24
c = 6404180

with open("value") as f:
    values_ = f.read().split("\n")

with open("weight") as f:
    weights_ = f.read().split("\n")

values = list(map(int, values_))
weights = list(map(int, weights_))


#f(i,v) 表示从前i件中挑选出使得价值为v,并且是size最小, 如果找不到就无穷大
#f(i,v) 表示
#V = max(v)
#复杂度为(n**2 * V)
def get_Solution(j):
    choice = [0]*n
    for i in range(n-1, 0, -1):
        if dp[i][j] != dp[i-1][j]:
            choice[i] = 1
            j = j - newValues[i]
        if j == newValues[0]:
            choice[0] = 1
    return choice

if __name__ == "__main__":
    V = max(values)
    alpha = 0.1
    K = (alpha*V)/n
    newValues = [math.floor((value*n)/(alpha*V)) for value in values]
    print(values)
    print(newValues)
    target = 0
    newV = max(newValues)
    dp = [[sys.maxsize]*(n*newV) for __ in range(n)]
    dp[0][newValues[0]] = weights[0]
    # print(dp)
    for i in range(1,n):
        for j in range(n*newV):
            if j - newValues[i] >= 0:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-newValues[i]]+weights[i])
            else:
                dp[i][j] = dp[i-1][j]
            
            if dp[i][j] <= c:
                # print(i,j)
                # print(dp[i][j])
                target = j
    print(target)
    choice = get_Solution(target)
    print(choice)
    total = sum([i*j for i,j in zip(values, choice)])
    print(total)

启发式算法

模拟退火

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/env python3
import sys
import random
import math

n = 24
c = 6404180
res = 13549094
# n = 15
# c = 750
# n = 10
# c = 165

with open("value_{}_{}".format(n, c)) as f:
    values_ = f.read().split("\n")

with open("weight_{}_{}".format(n, c)) as f:
    weights_ = f.read().split("\n")

values = list(map(int, values_))
weights = list(map(int, weights_))


alpha = 0.999
initTemperature = 1000
loops = 10000
smloop = 100

sol = [0]*n
temperature = initTemperature
loop = 0
maxValue = 0
final_sol = None
while loop < loops:
    temperature = temperature*alpha
    for i in range(smloop):
        index = random.choice(range(n))
        if sol[index] == 0:
            sol[index] = 1
            weight_sum = sum([i*j for i,j in zip(weights, sol)])
            if weight_sum <= c:
                value_sum = sum([i*j for i,j in zip(values, sol)])
                if value_sum > maxValue:
                    maxValue = value_sum
                    final_sol = sol[:]
            else:
                sol[index] = 0
                continue
        else:#sol[index] == 1, 1 -> 0
            #px - py = values[index]
            if random.random() > math.exp(-values[index]/temperature):
                sol[index] = 0
    loop = loop + 1
print(final_sol)
print(sum([i*j for i,j in zip(values, final_sol)]))

Tabu

禁忌搜索非常依赖参数，当我把循环次数设置为2000，listsize设置为2000前两个才能达到最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#!/usr/bin/env python3
import sys
import random
import math
from collections import deque

n = 24
c = 6404180
res = 13549094
# n = 15
# c = 750
# n = 10
# c = 165

with open("value_{}_{}".format(n, c)) as f:
    values_ = f.read().split("\n")

with open("weight_{}_{}".format(n, c)) as f:
    weights_ = f.read().split("\n")

values = list(map(int, values_))
weights = list(map(int, weights_))

def nerbo(sol):
    res = []
    for i in range(n):
        tmp = sol[:]
        tmp[i] = ~tmp[i] + 2
        res.append(tmp)
    return res

def tabuSearch(sol):
    final_sol = None
    final_val = 0
    loop = 0
    current_sol = sol
    while loop < loops:
        # print("current_sol: ", current_sol)
        nerbos = nerbo(current_sol)
        current_val = 0
        for ner in nerbos:
            # print(ner)
            if ner in tabuList:
                continue
            weight_sum = sum([i*j for i,j in zip(weights, ner)])
            if weight_sum > c:
                continue
            value_sum = sum([i*j for i,j in zip(values, ner)])
            # print(value_sum)
            if value_sum > current_val:
                current_val = value_sum
                current_sol = ner
        tabuList.append(current_sol)
        # print(tabuList)
        # print(current_sol)
        # print(current_val)
        if final_val < current_val:
            final_val = current_val
            final_sol = current_sol
        loop = loop + 1
    print(final_sol, final_val)
    return final_sol, final_val
                
        
def test():
    test_sol = [0]*n
    ner = nerbo(test_sol)
    print(ner)

if __name__ == "__main__":
    tabuList = deque(maxlen=2000)
    loops = 2000

    sol = [0]*n
    final_sol = None
    tabuSearch(sol)

在上述的参数下跑n=24的情况，得到的效果比较差。

然后又换了一种老师在ppt上讲的，大致翻译下来就是显示贪心算法，按照$v_i/w_i$ 从大大小往背包里装，同时把装进去的加到tabulist里面，然后再把$v_i/w_i$ 从背包里面拿出去，这里老师还判断了是不是在tabulist里面，我实现了发现效果不行，我把放入和拿出分别设置了一个tabulist效果也不行。如果初始值设置为全0那么跑出来的结果就是贪心算法的结果，如果是随机的初试结果，效果会好那么一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#!/usr/bin/env python3
import sys
import random
import math
from collections import deque, OrderedDict

n = 24
c = 6404180
res = 13549094
n = 15
c = 750
# n = 10
# c = 165

with open("value_{}_{}".format(n, c)) as f:
    values_ = f.read().split("\n")

with open("weight_{}_{}".format(n, c)) as f:
    weights_ = f.read().split("\n")

values = list(map(int, values_))
weights = list(map(int, weights_))

def nerbo(sol):
    res = []
    for i in range(n):
        tmp = sol[:]
        tmp[i] = ~tmp[i] + 2
        res.append(tmp)
    return res

def tabuSearch(sol):
    final_sol = None
    final_val = 0
    loop = 0
    while loop < loops:
        for key in vw:
            weight_sum = sum([i*j for i,j in zip(weights, sol)])
            print(tabuListIn)
            print(sol)
            print(weight_sum)
            if vw[key] not in tabuListIn:
                if weight_sum + weights[vw[key]] <= c and sol[vw[key]] != 1:
                    sol[vw[key]] = 1
                    value_sum = sum([i*j for i,j in zip(values, sol)])
                    tabuListIn.append(vw[key])
                    if value_sum > final_val:
                        final_val = value_sum
                        final_sol = sol[:]
        print("-"*25)
        for key in vw:
            if sol[vw[key]] == 1 and vw[key] not in tabuListOut:
                sol[vw[key]] = 0
                print(tabuListOut)
                tabuListOut.append(vw[key])
                print(sol)
                break
        print("*"*25)   

        loop = loop + 1
        print(loop)
    print(final_val, final_sol)
                
        
def test():
    test_sol = [0]*n
    ner = nerbo(test_sol)
    print(ner)

if __name__ == "__main__":
    length = 8
    tabuListIn = deque(maxlen=length)
    tabuListOut = deque(maxlen=4)
    vw = OrderedDict()    
    tmpd = {}
    for i in range(n):
        tmpd[values[i]/weights[i]] = i
    # print(tmpd)
    keys = list(tmpd.keys())
    keys.sort(reverse=True)
    for key in keys:
        vw[key] = tmpd[key]
    
    # print(vw)
    sol = [0]*n
    # for i in range(n):
    #     index = random.randint(0,n-1)
    #     sol[index] = 1
    #     weight_sum = sum([i*j for i,j in zip(weights, sol)])
    #     if weight_sum > c:
    #         sol[index] = 0
    print(sol)
    loops = 10
    tabuSearch(sol)

结果比较

暴力 $F(i,c)$ $F(i,v)$ FPTAS SA Tabu
n=10,c=165 309 309 309 309 309 309
n=15,c=750 1458 1458 1458 1458 1458 1458
n=24,c=6404180 N/A N/A N/A 13549094 13518963 13390333

从上面可以看到当数据比较大时，普通算法不能在可接受的时间内计算出结果。

总上FPTAS的效果最佳（求解出的都是最有结果），SA次之，可能加大循环次数能再提高点精度。就启发式算法而言，模拟退火要优于禁忌搜索。

当第一种禁忌搜索算法调整参数n=50000， maxlen=20000的时候能跑出一组为13518963的结果

有时间再补个遗传变异算法。

参考