背包 - 节省时间和内存(Knapsack - save time and memory)

根据维基百科和我去通过其他来源，则需要矩阵m[n][W] ; n -物品和数量W背包的总容量- 。 这个矩阵得到真正的大，有时太大，处理它的C程序。 我知道，动态编程基于节省时间的记忆，但仍然是有你在那里可以节省时间和内存中的任何解决方案？

对于伪代码背包问题：

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for j from 0 to W do
  m[0, j] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    if w[i] <= j then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for

比方说，那个W = 123456789和n = 100。在这种情况下，我们得到真正的大矩阵m [100] [123456789]。 我在想如何实现这一点，但最好的，我在我的脑海只是保存哪些项目与一个位（0/1）来选择。 这可能吗？ 或者是有这个问题的任何其他的方法呢？

int32 -> 32 * 123456789 * 100 bits
one_bit -> 1 * 123456789 * 100 bits

我希望这不是愚蠢的问题，并感谢你的努力。

编辑-工作的C代码：

    long int i, j;
    long int *m[2];
    m[0] = (long int *) malloc(sizeof(long int)*(W+1));
    m[1] = (long int *) malloc(sizeof(long int)*(W+1));
    for(i = 0; i <= W; i++){
        m[0][i] = 0;
    }

    int read = 0;
    int write = 1;
    int tmp;

    long int percent = (W+1)*(n)/100;
    long int counter = 0;

    for(i = 1; i <= n; i++){
        for(j = 0; j <= W; j++){
            if(w[i-1] <= j){
                m[write][j] = max(m[read][j],(v[i-1]) + m[read][j-(w[i-1])]);
            }else{
                m[write][j] = m[read][j];
            }
            counter++;
            if(counter == percent){
                printf(".");    //printing dot (.) for each percent
                fflush(stdout);
                counter = 0;
            }
        }
        tmp = read;
        read = write;
        write = tmp;
    }

    printf("\n%ld\n", m[read][W]);

    free(m[0]);
    free(m[1]);

Answer 1:

背包问题可以使用解决O(W)的空间。
在迭代中的每个步骤只需要2行-的阵列的电流状态m[i]和m[i + 1]

current = 1
int m[2][W]
set NONE for all elements of m # that means we are not able to process this state
m[0][0] = 0 # this is our start point, initially empty knapsack

FOR i in [1..n] do
    next = 3 - current; /// just use 1 or 2 based on the current index
    for j in [0...W] do
       m[next][j] = m[current][j]
    FOR j in [w[i]..W] do
       if m[current][j - w[i]] is not NONE then  # process only reachable positions
           m[next][j] = max(m[next][j], m[current][j - w[i]] + v[i]);
    current = next; /// swap current state and the produced one

此外，也可以只使用1阵列。 这里是伪代码

FOR i in [1..n] do
    FOR j in [w[i]..W] do
       m[j] = max(m[j], m[j - w[i]] + v[i]);

Answer 2:

可以从米减小空间的使用[100] [123456789]成m [2] [123456789]通过该观察：

看看这部分代码，在任何时候，你只需要参考矩阵的两行i和i - 1

if w[i] <= j then
  m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
else
  m[i, j] := m[i-1, j]
end if

您可以使用这一招：

int current = 1;


//.........
if w[i] <= j then
  m[current, j] := max(m[1 - current, j], m[1 - current, j-w[i]] + v[i])
else
  m[i, j] := m[1 - current, j]
end if
current = 1 - current;

文章来源: Knapsack - save time and memory