通过Pisinger快速解决方案，以子集和算法 [英] Fast solution to Subset sum algorithm by Pisinger

问题描述

这是一个后续行动，我的previous 问题。我仍然觉得很有意思的问题，因为有一个算法，值得更多的关注，我在这里张贴。

从维基百科：对于每一个喜的情况下是积极的，受限于相同的恒定，Pisinger发现了一个线性时间的算法。的

有一个不同的纸张，这似乎说明了同样的算法，但它是一个有点难以阅读对我来说，所以请 - 没有人知道怎么翻译，从第4页（ balsub ）进入工作实施？

下面是几个指针我收集迄今：

http://www.diku.dk/~pisinger/95-6。 PS （纸）
http://stackoverflow.com/a/9952759/1037407
http://www.diku.dk/hjemmesider/ansatte/pisinger/ codes.html

PS：我真的不坚持precisely这个算法，因此，如果您知道任何其他类似的高性能算法，请随时提出它吼叫

。

修改

这是的code一个Python版本贴娄由oldboy：

 类视图（对象）：
    高清__init __（个体经营，序列，开始）：
        self.sequence，self.start =序列，开始
    高清__getitem __（个体经营，指数）：
        回报self.sequence [指数+ self.start]
    高清__setitem __（个体经营，指数值）：
        self.sequence [指数+ self.start] =价值

高清balsub（W，C）：
    '''均衡算法由大卫Pisinger子集和问题
    W精品背包'''的=权重，C =容量
    N = LEN（W）
    断言N'GT; 0
    sum_w = 0
    使r = 0
    对于WJ在W：
        断言WJ＆GT; 0
        sum_w + = WJ
        断言WJ＆LT; = C
        R = MAX（R，WJ）
    断言sum_w＆GT; C
    B = 0
    w_bar = 0
    而w_bar + W [B]＆LT; = C：
        w_bar + =瓦特并[b]
        B + 1 =
    S = [[0] * 2 *在范围r为I（N  -  B + 1）]
    s_b_1 =视图（S [0]，R  -  1）
    对于在范围亩（-R + 1，1）：
        s_b_1 [μ= -1
    对于在范围亩（1，R + 1）：
        s_b_1 [μ= 0
    s_b_1 [w_bar  -  C] = B
    在t范围内（B，N）：
        s_t_1 =视图（S [T  -  B]，R  -  1）
        S_T =视图（S [T  -  B + 1]，R ​​ -  1）
        对于在范围亩（-R + 1，R + 1）：
            S_T微米= s_t_1微米
        对于在范围亩（-R + 1，1）：
            mu_prime =亩+ W [T]
            S_T [mu_prime] = MAX（S_T [mu_prime]，s_t_1μ）
        对于在范围亩（瓦特[吨]，0，-1）：
            对于j的范围（S_T微米 -  1，s_t_1微米 -  1，-1）：
                mu_prime =亩 -  W [J]。
                S_T [mu_prime] = MAX（S_T [mu_prime]，J）
    解决=假
    Z = 0
    s_n_1 =视图（S [N  -  B]，R  -  1）
    而Z取代; = -r + 1：
        如果s_n_1 [Z]≥= 0：
            解决= TRUE
            打破
        ž -  = 1
    如果解决：
        打印Ç+ Z
        打印传单N
        X = [虚假] * N
        对于j在范围（0，b）的
            X [J] = TRUE
        在t在范围（N  -  1，B  -  1，-1）：
            S_T =视图（S [T  -  B + 1]，R ​​ -  1）
            s_t_1 =视图（S [T  -  B]，R  -  1）
            而真正的：
                J = S_T [Z]
                断言J＆GT; = 0
                z_unprime = Z + W [J]。
                如果z_unprime＆GT; R或J＆GT; = S_T [z_unprime]：
                    打破
                Z = z_unprime
                X [J] = FALSE
            z_unprime = Z  -  W [T]
            如果z_unprime＆GT = -r + 1和s_t_1 [z_unprime]≥= S_T [Z]：
                Z = z_unprime
                X [T] = TRUE
        对于j的范围（n）的：
            打印X [J]，W [J]。
 

解决方案

  //输入：
// C（背包的容量）
// N（件数）
// W_1（重量项目1）
// ...
// w_n（重量项的n）
//
//输出：
// Z（最优解）
//ñ
// X_1（指标为第1项）
// ...
// x_n（指标项目N）

＃包括＆LT;算法＆GT;
＃包括＆LT;＆了cassert GT;
＃包括＆LT;的iostream＆GT;
＃包括＆LT;载体＆GT;

使用名字空间std;

诠释的main（）{
  INT C = 0;
  CIN＆GT;＆GT; C;
  INT N = 0;
  CIN＆GT;＆GT; N;
  断言（正大于0）;
  矢量＆lt; int的＆GT; W（N）;
  INT sum_w = 0;
  INT R = 0;
  为（诠释J = 0; J＆n种++ j）条{
    CIN＆GT;＆GT; W [J]。
    断言（W [J]大于0）;
    sum_w + = W [J]。
    断言（W [J]＆LT; = C）;
    R = MAX（R，W [J]）;
  }
  断言（sum_w＆GT; C）;
  INT B：
  INT w_bar = 0;
  对于（B = 0; w_bar + W [B]＆LT; = C ++ B）{
    w_bar + =瓦特并[b];
  }
  矢量＆lt;矢量＆lt; INT＆GT; ＆GT; S（N  -  B + 1，矢量＆lt; INT＆GT;（2 * R））;
  矢量＆lt; INT＆GT;：迭代s_b_1 = S [0] .begin（）+（R  -  1）;
  对于（INT亩= -r + 1;万亩＆LT; = 0; ++亩）{
    s_b_1 [μ= -1;
  }
  对于（INT亩= 1;万亩＆LT; = R ++亩）{
    s_b_1 [μ= 0;
  }
  s_b_1 [w_bar  -  C] = B;
  对于（INT T = B：T＆n种++ T）{
    矢量＆lt; INT＆GT; ::为const_iterator s_t_1 = S [吨 -  B] .begin（）+（R  -  1）;
    矢量＆lt; INT＆GT; :: S_T =迭代器[吨 -  B + 1] .begin（）+（R  -  1）;
    对于（INT亩= -r + 1;万亩＆LT; = R ++亩）{
      S_T微米= s_t_1微米;
    }
    对于（INT亩= -r + 1;万亩＆LT; = 0; ++亩）{
      INT mu_prime =亩+ W [T]
      S_T [mu_prime] =最大值（S_T [mu_prime]，s_t_1μ）;
    }
    对于（INT亩= W [T];万亩＆GT; = 1; --mu）{
      对于（INT J = S_T微米 -  1; J＆GT; = s_t_1微米; --j）{
        INT mu_prime =亩 -  W [J]。
        S_T [mu_prime] = MAX（S_T [mu_prime]，J）;
      }
    }
  }
  布尔解决= FALSE;
  INT Z者除外;
  矢量＆lt; INT＆GT; ::为const_iterator s_n_1 = S [N  -  B] .begin（）+（R  -  1）;
  对于（Z = 0; Z取代; = -r + 1; --z）{
    如果（s_n_1 [Z]≥= 0）{
      解决= TRUE;
      打破;
    }
  }
  如果（解决）{
    COUT＆LT;＆LT; C + z，其中;＆LT; '\ N'＆LT;＆LT; N'LT;＆LT; '\ N';
    矢量＆lt;布尔＆GT; X（N，FALSE）;
    对于（INT J = 0; J＆LT; B; ++ j）条X [J] =真;
    对于（INT T = N  -  1; T＆GT; = B; --t）{
      矢量＆lt; INT＆GT; :: S_T = S为const_iterator [吨 -  B + 1] .begin（）+（R  -  1）;
      矢量＆lt; INT＆GT; ::为const_iterator s_t_1 = S [吨 -  B] .begin（）+（R  -  1）;
      而（真）{
        INT J = S_T [Z]。
        断言（J＆GT; = 0）;
        INT z_unprime = Z + W [J]。
        如果（z_unprime＆GT; R || J＆G​​T; = S_T [z_unprime]）破;
        Z = z_unprime;
        X [J] = FALSE;
      }
      INT z_unprime = Z  -  W [T];
      如果（z_unprime＆GT = -r +1安培;＆安培; s_t_1 [z_unprime]≥= S_T [Z]）{
        Z = z_unprime;
        X [T] =真;
      }
    }
    为（诠释J = 0; J＆n种++ j）条{
      COUT＆LT;＆LT; X [J]＆LT;＆LT; '\ N';
    }
  }
}
 

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)
http://stackoverflow.com/a/9952759/1037407
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]

解决方案

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

这篇关于通过Pisinger快速解决方案，以子集和算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！