Questo è un follow-up del mio precedente question. Trovo ancora un problema molto interessante e poiché c'è un algoritmo che merita più attenzione, lo sto postando qui.Algoritmo di somme sommarie di Pisinger Soluzione rapida a subset
Da Wikipedia: Nel caso in cui ogni xi sia positivo e limitato dalla stessa costante, Pisinger ha trovato un algoritmo di tempo lineare.
V'è una carta diversa, che sembra descrivere lo stesso algoritmo, ma è un po 'difficile da leggere per me quindi per favore - qualcuno sa come tradurre la pseudo-codice da pagina 4 (balsub
) in esecuzione di lavoro?
Ecco paio di puntatori ho raccolto finora:
http://www.diku.dk/~pisinger/95-6.ps (la carta)
https://stackoverflow.com/a/9952759/1037407
http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html
PS: non ho davvero insistere proprio su questo algoritmo, quindi se siete a conoscenza di qualsiasi altro algoritmo altrettanto performante, sentitevi liberi di suggerirlo sotto.
Modifica
Questa è una versione Python del codice postato muggito da Oldboy:
class view(object):
def __init__(self, sequence, start):
self.sequence, self.start = sequence, start
def __getitem__(self, index):
return self.sequence[index + self.start]
def __setitem__(self, index, value):
self.sequence[index + self.start] = value
def balsub(w, c):
'''A balanced algorithm for Subset-sum problem by David Pisinger
w = weights, c = capacity of the knapsack'''
n = len(w)
assert n > 0
sum_w = 0
r = 0
for wj in w:
assert wj > 0
sum_w += wj
assert wj <= c
r = max(r, wj)
assert sum_w > c
b = 0
w_bar = 0
while w_bar + w[b] <= c:
w_bar += w[b]
b += 1
s = [[0] * 2 * r for i in range(n - b + 1)]
s_b_1 = view(s[0], r - 1)
for mu in range(-r + 1, 1):
s_b_1[mu] = -1
for mu in range(1, r + 1):
s_b_1[mu] = 0
s_b_1[w_bar - c] = b
for t in range(b, n):
s_t_1 = view(s[t - b], r - 1)
s_t = view(s[t - b + 1], r - 1)
for mu in range(-r + 1, r + 1):
s_t[mu] = s_t_1[mu]
for mu in range(-r + 1, 1):
mu_prime = mu + w[t]
s_t[mu_prime] = max(s_t[mu_prime], s_t_1[mu])
for mu in range(w[t], 0, -1):
for j in range(s_t[mu] - 1, s_t_1[mu] - 1, -1):
mu_prime = mu - w[j]
s_t[mu_prime] = max(s_t[mu_prime], j)
solved = False
z = 0
s_n_1 = view(s[n - b], r - 1)
while z >= -r + 1:
if s_n_1[z] >= 0:
solved = True
break
z -= 1
if solved:
print c + z
print n
x = [False] * n
for j in range(0, b):
x[j] = True
for t in range(n - 1, b - 1, -1):
s_t = view(s[t - b + 1], r - 1)
s_t_1 = view(s[t - b], r - 1)
while True:
j = s_t[z]
assert j >= 0
z_unprime = z + w[j]
if z_unprime > r or j >= s_t[z_unprime]:
break
z = z_unprime
x[j] = False
z_unprime = z - w[t]
if z_unprime >= -r + 1 and s_t_1[z_unprime] >= s_t[z]:
z = z_unprime
x[t] = True
for j in range(n):
print x[j], w[j]
Bene .... cosa posso dire. Questo è buono come se fosse stato scritto dall'autore originale. Sono davvero, davvero grato, è un gran bel pezzo di codice. Un'ultima domanda: è anche possibile restituire tutti gli articoli che hanno contribuito alla somma finale? –
Fatto, ma non ben collaudato. Procedi con cautela. – oldboy
+1. _Molto bella. Dato che inizialmente stavamo gettando questo in giro in Python, sto valutando di lasciar cadere una versione aggiornata che include la soluzione invece di solo "balsub". – MrGomez