0%

01背包问题四类解法

问题描述

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

在满足$\sum_i^n w_i*x_i \leq c$ 的情况下求 $max(\sum_i^n vi*x_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的结果

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

参考