2012-04-01 13 views
9

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] 

risposta

10
// Input: 
// c (capacity of the knapsack) 
// n (number of items) 
// w_1 (weight of item 1) 
// ... 
// w_n (weight of item n) 
// 
// Output: 
// z (optimal solution) 
// n 
// x_1 (indicator for item 1) 
// ... 
// x_n (indicator for item n) 

#include <algorithm> 
#include <cassert> 
#include <iostream> 
#include <vector> 

using namespace std; 

int main() { 
    int c = 0; 
    cin >> c; 
    int n = 0; 
    cin >> n; 
    assert(n > 0); 
    vector<int> w(n); 
    int sum_w = 0; 
    int r = 0; 
    for (int j = 0; j < n; ++j) { 
    cin >> w[j]; 
    assert(w[j] > 0); 
    sum_w += w[j]; 
    assert(w[j] <= c); 
    r = max(r, w[j]); 
    } 
    assert(sum_w > c); 
    int b; 
    int w_bar = 0; 
    for (b = 0; w_bar + w[b] <= c; ++b) { 
    w_bar += w[b]; 
    } 
    vector<vector<int> > s(n - b + 1, vector<int>(2 * r)); 
    vector<int>::iterator s_b_1 = s[0].begin() + (r - 1); 
    for (int mu = -r + 1; mu <= 0; ++mu) { 
    s_b_1[mu] = -1; 
    } 
    for (int mu = 1; mu <= r; ++mu) { 
    s_b_1[mu] = 0; 
    } 
    s_b_1[w_bar - c] = b; 
    for (int t = b; t < n; ++t) { 
    vector<int>::const_iterator s_t_1 = s[t - b].begin() + (r - 1); 
    vector<int>::iterator s_t = s[t - b + 1].begin() + (r - 1); 
    for (int mu = -r + 1; mu <= r; ++mu) { 
     s_t[mu] = s_t_1[mu]; 
    } 
    for (int mu = -r + 1; mu <= 0; ++mu) { 
     int mu_prime = mu + w[t]; 
     s_t[mu_prime] = max(s_t[mu_prime], s_t_1[mu]); 
    } 
    for (int mu = w[t]; mu >= 1; --mu) { 
     for (int j = s_t[mu] - 1; j >= s_t_1[mu]; --j) { 
     int mu_prime = mu - w[j]; 
     s_t[mu_prime] = max(s_t[mu_prime], j); 
     } 
    } 
    } 
    bool solved = false; 
    int z; 
    vector<int>::const_iterator s_n_1 = s[n - b].begin() + (r - 1); 
    for (z = 0; z >= -r + 1; --z) { 
    if (s_n_1[z] >= 0) { 
     solved = true; 
     break; 
    } 
    } 
    if (solved) { 
    cout << c + z << '\n' << n << '\n'; 
    vector<bool> x(n, false); 
    for (int j = 0; j < b; ++j) x[j] = true; 
    for (int t = n - 1; t >= b; --t) { 
     vector<int>::const_iterator s_t = s[t - b + 1].begin() + (r - 1); 
     vector<int>::const_iterator s_t_1 = s[t - b].begin() + (r - 1); 
     while (true) { 
     int j = s_t[z]; 
     assert(j >= 0); 
     int z_unprime = z + w[j]; 
     if (z_unprime > r || j >= s_t[z_unprime]) break; 
     z = z_unprime; 
     x[j] = false; 
     } 
     int z_unprime = z - w[t]; 
     if (z_unprime >= -r + 1 && s_t_1[z_unprime] >= s_t[z]) { 
     z = z_unprime; 
     x[t] = true; 
     } 
    } 
    for (int j = 0; j < n; ++j) { 
     cout << x[j] << '\n'; 
    } 
    } 
} 
+0

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? –

+0

Fatto, ma non ben collaudato. Procedi con cautela. – oldboy

+0

+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

-2

codice grande uomo, ma a volte si è schiantato in questo codeblock

for (mu = w[t]; mu >= 1; --mu) 
    { 
     for (int j = s_t[mu] - 1; j >= s_t_1[mu]; --j) 
     { 
      if (j >= w.size()) 
      { // !!! PROBLEM !!! 

      } 


      int mu_prime = mu - w[j]; 

      s_t[mu_prime] = max(s_t[mu_prime], j); 
     } 
    } 

...

+0

Si prega di aggiungere un motivo per l'errore se è possibile. Inoltre, quando sono utili anche i dettagli del crash del codice. –

+1

Davvero non lo so, ma ho messo questo controllo \t \t \t \t if (j bajone

+2

Inserisci le informazioni nella tua risposta con [* modifica *] (http://stackoverflow.com/posts/20498481/edit). –