-
Notifications
You must be signed in to change notification settings - Fork 36
/
fptas.py
117 lines (99 loc) · 3.38 KB
/
fptas.py
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import math
class KnapsackDP(object):
""" 背包问题的动态规划算法.
"""
def __init__(self, w, p, W):
"""
:param w: 物品大小, list
:param p: 物品价值, list
:param W: 背包大小, int
"""
self._w = w
self._p = p
self._W = W
self._n = len(self._w)
self._f = self._init_recurrence_formula()
self._result = None
def _init_recurrence_formula(self):
n = len(self._w)
f = [[]] * n
max_p = max(self._p)
for i in range(n):
f[i] = [math.inf] * n * max_p
f[0][0] = 0 # !
f[0][self._p[0]] = self._w[0]
return f
def solve(self):
n = len(self._w)
max_p = max(self._p)
# key = profit, value = 达到此profit所包含的一个item
for i in range(n-1):
for j in range(n * max_p):
if self._p[i+1] <= j:
self._f[i+1][j] = min(self._f[i][j],
self._f[i][j-self._p[i+1]] + self._w[i+1])
else:
self._f[i+1][j] = self._f[i][j]
self._result = self._get_result( self._get_profit())
return self
def _get_profit(self):
weights = self._f[len(self._w) - 1]
# print(weights)
m = len(weights)
for i in range(m):
value = m - 1 - i
if weights[value] <= self._W:
return value
def _get_result(self, profit):
result = []
for i in range(self._n-1,0,-1):
if self._f[i][profit] > self._f[i-1][profit] or self._f[i-1][profit] == math.inf:
result.append(i)
profit -= self._p[i]
return result
def get_result(self):
return self._result
def print_result(self):
print("Packed items:", self._result)
print("Total profit:", sum([self._p[i] for i in self._result]))
print("Total weight:", sum([self._w[i] for i in self._result]))
class KnapsackFPTAS(object):
""" 动态规划FPTAS.
近似比: ALG >= (1-epsilon)OPT, 时间复杂度 = O(n^2 * floor(n/epsilon))
"""
def __init__(self, w, p, W):
"""
:param w: 物品大小, list
:param p: 物品价值, list
:param W: 背包大小, int
"""
self._w = w
self._p = p
self._W = W
self._n = len(self._w)
self._result = None
def solve(self, epsilon):
k = epsilon * max(self._p) / len(self._w)
p1 = [int(x/k) for x in self._p]
dp = KnapsackDP(self._w, p1, self._W).solve()
self._result = dp.get_result()
return self
def print_result(self):
print("Packed items:", self._result)
print("Total profit:", sum([self._p[i] for i in self._result]))
print("Total weight:", sum([self._w[i] for i in self._result]))
if __name__ == '__main__':
W = 180 #150
p = [505, 352, 458, 220, 354, 414, 498, 545, 473, 543]
w = [23, 26, 20, 18, 32, 27, 29, 26, 30, 27]
import time
print("==== DP solution ====")
t1 = time.time()
knapsack = KnapsackDP(w, p, W).solve()
print(">> time cost:", time.time() - t1)
knapsack.print_result()
print("==== FPTAS solution ====")
t1 = time.time()
p = KnapsackFPTAS(w, p, W).solve(0.5)
print(">> time cost:", time.time() - t1)
p.print_result()