import numpy as np
import pandas as pd
import math
from numpy import inf
pd.set_option('display.max_rows', 500)
pd.set_option('display.max_columns', 500)
pd.set_option('display.width', 1000)
def greedy_fractional_knapsack(W, c, w):
assert c.shape == w.shape
assert W <= w.sum()
ratios = [(index, c / float(w)) for index, (c, w) in enumerate(zip(c,w))]
ratios = sorted(ratios, key=lambda x: x[1], reverse=True)
df = pd.DataFrame(data=np.array(ratios))
df.columns = ['index', 'ratio']
display(df)
x = np.zeros(w.shape)
total_weight = 0
for index, ratio in ratios:
if total_weight + w[index] <= W:
x[index] = 1
total_weight += w[index]
else:
x[index] = (W - total_weight) / w[index]
return x
c = [2,1,3,2]
c = np.array(c)
w = [1,3,4,2]
w = np.array(w)
W = 8
x = greedy_fractional_knapsack(W, c, w)
| index | ratio | |
|---|---|---|
| 0 | 0.0 | 2.000000 |
| 1 | 3.0 | 1.000000 |
| 2 | 2.0 | 0.750000 |
| 3 | 1.0 | 0.333333 |
df = pd.DataFrame(data=x)
df.columns = ['items']
display(df)
| items | |
|---|---|
| 0 | 1.000000 |
| 1 | 0.333333 |
| 2 | 1.000000 |
| 3 | 1.000000 |
def greedy_knapsack(W, c, w):
assert c.shape == w.shape
assert W <= w.sum()
ratios = [(index, c / float(w)) for index, (c, w) in enumerate(zip(c,w))]
ratios = sorted(ratios, key=lambda x: x[1], reverse=True)
x = np.zeros(w.shape)
x_total_weight = 0
y = np.zeros(w.shape)
y_total_weight = 0
for index, ratio in ratios:
if x_total_weight + w[index] <= W:
x[index] = 1
x_total_weight += w[index]
else:
y[index] = 1
y_total_weight += w[index]
if x_total_weight >= y_total_weight:
return x
else:
return y
c = [2,1,3,2]
c = np.array(c)
w = [1,3,4,2]
w = np.array(w)
W = 8
x = greedy_knapsack(W, c, w)
df = pd.DataFrame(data=x)
df.columns = ['items']
display(df)
| items | |
|---|---|
| 0 | 1.0 |
| 1 | 0.0 |
| 2 | 1.0 |
| 3 | 1.0 |
def dynamic_knapsack(W, C, w, c):
(n, ) = w.shape
m = np.zeros((n + 1,C + 1))
x = np.zeros((n + 1,C + 1))
m[0,] = float('inf')
m[0,0] = 0
for j in range(1, n + 1):
j_bar = j -1
print(f'Next iteration: {j} {64 * "="}')
for k in range(C + 1):
x[j,k] = 0
m[j,k] = m[j-1, k]
for k in range(c[j_bar], C + 1):
print(f'm[{j-1}, {k-c[j_bar]}]: {m[j-1, k-c[j_bar]]} + {w[j_bar]} <= min({W},{m[j,k]})')
if (m[j-1, k-c[j_bar]] + w[j_bar]) <= min(W, m[j,k]):
m[j,k] = m[j-1, k-c[j_bar]] + w[j_bar]
x[j,k] = 1
print(f'm[{j},{k}] : {m[j,k]}')
m[m == inf] = -1
k = np.amax(np.where(m[n,] > -1))
max_profit = k
items = []
print(f'Get vector x {64 * "="}')
while n > 0:
print(f'Check x[{n}, {k}]: {x[n, k]}')
item = 0
if x[n, k] == 1:
print(f'Include item: {n}')
item = 1
k -= c[n-1]
items.append(item)
n -= 1
print(f'DONE {64 * "="}')
return max_profit, m, x, np.array(items)[::-1]
c = [2,1,3,2]
c = np.array(c)
w = [1,3,4,2]
w = np.array(w)
W = 8
C = np.sum(c)
profit, m, x, items = dynamic_knapsack(W, C, w, c)
print(f'Maximum profit is {profit}')
print(f'Maximum capacity is {np.amax(m)}')
print(f'Selected items are {items}')
df = pd.DataFrame(data=items)
df.columns = ['items']
display(df)
Next iteration: 1 ================================================================ m[0, 0]: 0.0 + 1 <= min(8,inf) m[1,2] : 1.0 m[0, 1]: inf + 1 <= min(8,inf) m[1,3] : inf m[0, 2]: inf + 1 <= min(8,inf) m[1,4] : inf m[0, 3]: inf + 1 <= min(8,inf) m[1,5] : inf m[0, 4]: inf + 1 <= min(8,inf) m[1,6] : inf m[0, 5]: inf + 1 <= min(8,inf) m[1,7] : inf m[0, 6]: inf + 1 <= min(8,inf) m[1,8] : inf Next iteration: 2 ================================================================ m[1, 0]: 0.0 + 3 <= min(8,inf) m[2,1] : 3.0 m[1, 1]: inf + 3 <= min(8,1.0) m[2,2] : 1.0 m[1, 2]: 1.0 + 3 <= min(8,inf) m[2,3] : 4.0 m[1, 3]: inf + 3 <= min(8,inf) m[2,4] : inf m[1, 4]: inf + 3 <= min(8,inf) m[2,5] : inf m[1, 5]: inf + 3 <= min(8,inf) m[2,6] : inf m[1, 6]: inf + 3 <= min(8,inf) m[2,7] : inf m[1, 7]: inf + 3 <= min(8,inf) m[2,8] : inf Next iteration: 3 ================================================================ m[2, 0]: 0.0 + 4 <= min(8,4.0) m[3,3] : 4.0 m[2, 1]: 3.0 + 4 <= min(8,inf) m[3,4] : 7.0 m[2, 2]: 1.0 + 4 <= min(8,inf) m[3,5] : 5.0 m[2, 3]: 4.0 + 4 <= min(8,inf) m[3,6] : 8.0 m[2, 4]: inf + 4 <= min(8,inf) m[3,7] : inf m[2, 5]: inf + 4 <= min(8,inf) m[3,8] : inf Next iteration: 4 ================================================================ m[3, 0]: 0.0 + 2 <= min(8,1.0) m[4,2] : 1.0 m[3, 1]: 3.0 + 2 <= min(8,4.0) m[4,3] : 4.0 m[3, 2]: 1.0 + 2 <= min(8,7.0) m[4,4] : 3.0 m[3, 3]: 4.0 + 2 <= min(8,5.0) m[4,5] : 5.0 m[3, 4]: 7.0 + 2 <= min(8,8.0) m[4,6] : 8.0 m[3, 5]: 5.0 + 2 <= min(8,inf) m[4,7] : 7.0 m[3, 6]: 8.0 + 2 <= min(8,inf) m[4,8] : inf Get vector x ================================================================ Check x[4, 7]: 1.0 Include item: 4 Check x[3, 5]: 1.0 Include item: 3 Check x[2, 2]: 0.0 Check x[1, 2]: 1.0 Include item: 1 DONE ================================================================ Maximum profit is 7 Maximum capacity is 8.0 Selected items are [1 0 1 1]
| items | |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
df = pd.DataFrame(data=m)
df = df.replace(-1.0, "inf")
display(df)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0.0 | inf | inf | inf | inf | inf | inf | inf | inf |
| 1 | 0.0 | inf | 1.0 | inf | inf | inf | inf | inf | inf |
| 2 | 0.0 | 3.0 | 1.0 | 4.0 | inf | inf | inf | inf | inf |
| 3 | 0.0 | 3.0 | 1.0 | 4.0 | 7.0 | 5.0 | 8.0 | inf | inf |
| 4 | 0.0 | 3.0 | 1.0 | 4.0 | 3.0 | 5.0 | 8.0 | 7.0 | inf |
def fptas_knapsack(W, w, c, epsilon):
(n,) = w.shape
assert epsilon > 0
x = greedy_knapsack(W, c, w)
x_c = np.sum(x * c)
if x_c == 0:
return x
t = max(1, (epsilon * x_c) / n)
c_bar = [math.ceil(c / float(t)) for index, c in enumerate(c)]
C = (2 * x_c) / t
_, _, _, y = dynamic_knapsack(W, int(C), w, c_bar)
y_c = np.sum(y * c)
if x_c >= y_c:
return x
else:
return y
c = [2,1,3,2]
c = np.array(c)
w = [1,3,4,2]
w = np.array(w)
W = 8
x = fptas_knapsack(W, w, c, 1)
Next iteration: 1 ================================================================ m[0, 0]: 0.0 + 1 <= min(8,inf) m[1,2] : 1.0 m[0, 1]: inf + 1 <= min(8,inf) m[1,3] : inf m[0, 2]: inf + 1 <= min(8,inf) m[1,4] : inf m[0, 3]: inf + 1 <= min(8,inf) m[1,5] : inf m[0, 4]: inf + 1 <= min(8,inf) m[1,6] : inf m[0, 5]: inf + 1 <= min(8,inf) m[1,7] : inf m[0, 6]: inf + 1 <= min(8,inf) m[1,8] : inf Next iteration: 2 ================================================================ m[1, 0]: 0.0 + 3 <= min(8,inf) m[2,1] : 3.0 m[1, 1]: inf + 3 <= min(8,1.0) m[2,2] : 1.0 m[1, 2]: 1.0 + 3 <= min(8,inf) m[2,3] : 4.0 m[1, 3]: inf + 3 <= min(8,inf) m[2,4] : inf m[1, 4]: inf + 3 <= min(8,inf) m[2,5] : inf m[1, 5]: inf + 3 <= min(8,inf) m[2,6] : inf m[1, 6]: inf + 3 <= min(8,inf) m[2,7] : inf m[1, 7]: inf + 3 <= min(8,inf) m[2,8] : inf Next iteration: 3 ================================================================ m[2, 0]: 0.0 + 4 <= min(8,1.0) m[3,2] : 1.0 m[2, 1]: 3.0 + 4 <= min(8,4.0) m[3,3] : 4.0 m[2, 2]: 1.0 + 4 <= min(8,inf) m[3,4] : 5.0 m[2, 3]: 4.0 + 4 <= min(8,inf) m[3,5] : 8.0 m[2, 4]: inf + 4 <= min(8,inf) m[3,6] : inf m[2, 5]: inf + 4 <= min(8,inf) m[3,7] : inf m[2, 6]: inf + 4 <= min(8,inf) m[3,8] : inf Next iteration: 4 ================================================================ m[3, 0]: 0.0 + 2 <= min(8,1.0) m[4,2] : 1.0 m[3, 1]: 3.0 + 2 <= min(8,4.0) m[4,3] : 4.0 m[3, 2]: 1.0 + 2 <= min(8,5.0) m[4,4] : 3.0 m[3, 3]: 4.0 + 2 <= min(8,8.0) m[4,5] : 6.0 m[3, 4]: 5.0 + 2 <= min(8,inf) m[4,6] : 7.0 m[3, 5]: 8.0 + 2 <= min(8,inf) m[4,7] : inf m[3, 6]: inf + 2 <= min(8,inf) m[4,8] : inf Get vector x ================================================================ Check x[4, 6]: 1.0 Include item: 4 Check x[3, 4]: 1.0 Include item: 3 Check x[2, 2]: 0.0 Check x[1, 2]: 1.0 Include item: 1 DONE ================================================================
df = pd.DataFrame(data=x)
df.columns = ['items']
display(df)
| items | |
|---|---|
| 0 | 1.0 |
| 1 | 0.0 |
| 2 | 1.0 |
| 3 | 1.0 |