Fast solution to Subset sum algorithm by Pisinger

Question

This is a follow-up to my previous question. I still find it very interesting problem and as there is one algorithm which deserves more attention I'm posting it here.

From Wikipedia: For the case that each xi is positive and bounded by the same constant, Pisinger found a linear time algorithm.

There is a different paper which seems to describe the same algorithm but it is a bit difficult to read for me so please - does anyone know how to translate the pseudo-code from page 4 (balsub) into working implementation?

Here are couple of pointers I collected so far:

http://www.diku.dk/~pisinger/95-6.ps (the paper)
https://mcmap.net/q/656187/-fast-solution-to-subset-sum
http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html

PS: I don't really insist on precisely this algorithm so if you know of any other similarly performant algorithm please feel free to suggest it bellow.

Edit

This is a Python version of the code posted bellow by 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]

Degeneracy

Here is my open-source javascript solution for the linear time, iterative 2004 algorithm by Pisinger which solves subset sum for each x_i positive and bounded by some constant C: github.com/thorpep138/subset-sum-pisinger and npmjs.com/package/subset-sum-pisinger . It has an open test suite and follows precisely the algorithm outlined in link.springer.com/chapter/10.1007%2F978-3-540-24777-7_4 – Sparker

I tried running this code as python3 and it failed because of missing parentheses on the prints. Just letting you know in case you want to add them. – Balneology

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

Scuttle

Well....what can I say. This is as good as if it was written by the original author. I'm really, really thankful, it's a great piece of code. One last question: is it also possible to return all the items which contributed to the final sum? – Degeneracy

Done, but not well tested. Proceed with caution. – Scuttle

+1. Very nice. Since we were originally throwing this around in Python, I'm considering dropping an updated version that includes the solution instead of just balsub. – Praline

@MrGomez: please do! I'm doing the same already, I'm almost finished. Then, we can compare our versions and catch bugs from the translation. – Degeneracy

Too bad it doesn't have any real comments and is just a piece of code. – Kinetic

Without comments, this code might as well be missing the newlines too. – Puma

see this: #24474207 – Karmen

Answer 2

great code man, but it sometimes crashed in this 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);
        }
    }

...

Dobbins

Please add a reason for the failure if you can. Also, when does the code crash details would also be helpful. – Hyper

I realy dont know, but I put this check if (j < w.size()) { int mu_prime = mu - w[j]; s_t[mu_prime] = max(s_t[mu_prime], j); } and it works - same result set! – Dobbins

Put that info in your answer by editing it. – Hyper