9

これは私の前の質問へのフォローアップです。私はまだそれが非常に興味深い問題だと思っています.1つのアルゴリズムがもっと注目に値するので、ここに投稿しています.

ウィキペディアから:各 xi が正で、同じ定数で囲まれている場合、Pisinger は線形時間アルゴリズムを見つけました。

同じアルゴリズムを説明しているように見える別の論文がありますが、私には読むのが少し難しいのでお願いします.4ページの疑似コード（balsub）を実用的な実装に変換する方法を知っている人はいますか？

これまでに収集したいくつかのポインターを次に示します。

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

PS: 私はこのアルゴリズムを正確に主張しているわけではないので、他の同様のパフォーマンスのアルゴリズムを知っている場合は、遠慮なく以下に提案してください。

編集

これは、oldboy によって次のように投稿されたコードの Python バージョンです。

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]
4

2 に答える 2

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';
    }
  }
}
于 2012-04-03T16:20:14.693 に答える