Giải pháp nhanh cho thuật toán Tổng số phụ của Pisinger

Question

Đây là phần tiếp theo cho số question trước đó của tôi. Tôi vẫn tìm thấy nó rất thú vị vấn đề và như có một thuật toán mà đáng chú ý hơn tôi đang đăng nó ở đây.

Từ Wikipedia: Đối với trường hợp mỗi xi là dương và bị giới hạn bởi cùng một hằng số, Pisinger tìm thấy thuật toán thời gian tuyến tính.

Có một loại giấy khác có vẻ như mô tả cùng một thuật toán nhưng có một chút khó đọc cho tôi - vậy có ai biết cách dịch mã giả từ trang 4 (balsub) sang triển khai không?

Dưới đây là vài gợi ý tôi thu thập được cho đến nay:

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

PS: Tôi không thực sự nhấn mạnh vào chính xác thuật toán này vì vậy nếu bạn biết bất kỳ thuật toán thực hiện tương tự nào khác, vui lòng đề xuất thuật toán dưới đây.

Sửa

Đây là một phiên bản Python của mã đăng tải dưới đây bởi 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

lớn đang người đàn ông, nhưng đôi khi nó bị rơi trong codeblock này

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

...