Solución rápida al algoritmo suma Subset por Pisinger

Question

Esto es una continuación de mi question anterior. Todavía me parece un problema muy interesante y como hay un algoritmo que merece más atención, lo publico aquí.

De Wikipedia: Para el caso de que cada xi sea positivo y esté limitado por la misma constante, Pisinger encontró un algoritmo de tiempo lineal.

Hay un papel diferente, que parece describir el mismo algoritmo, pero es un poco difícil de leer para mí así que por favor - ¿alguien sabe cómo traducir el pseudo-código de la página 4 (balsub) en aplicación de trabajo?

Éstos son par de punteros que recoge hasta el momento:

http://www.diku.dk/~pisinger/95-6.ps (el papel)
https://stackoverflow.com/a/9952759/1037407
http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html

PS: Yo realmente no insistir en este algoritmo, precisamente por lo que si usted sabe de cualquier otro algoritmo de rendimiento similar, siéntase libre de sugerirlo a continuación.

Editar

Ésta es una versión de Python del código publicado abajo por 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] 

Answer 1

// 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'; 
    } 
    } 
} 

Answer 2

gran hombre código, pero a veces se estrelló en este bloque de código

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); 
     } 
    } 

...