背包 - 节省时间和内存 [英] Knapsack - save time and memory

问题描述

根据维基百科和其他来源我有经历了，你需要矩阵 M [N] [W] ; N - 项目数和是W - 总背包的容量。该矩阵得到真正的大，有时太大，处理它的C程序。我知道，动态编程是基于节省时间的记忆，但仍然是有你在那里可以节省时间和内存的任何解决方案？

伪$ C $下背包问题：

  //输入：
//值（存储在数组v）的
//重量（存储在数组w）
//不同项目数（n）的
//背包容量（W）
对于j从0到w请勿
  米[0，j]中：= 0
结束了
对于i从1到n做
  对于j从0到w请勿
    当w [1]  - ; = j的再
      米[I，J]：=最大值（米[I-1，j]的，米[I-1，J-瓦特[I] + V [I]）
    其他
      米[I，J]：=米[I-1，j]的
    如果结束
  结束了
结束了
 

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

  INT32  - ＆GT; 32 * 123456789 * 100位
one_bit  - ＆GT; 1 * 123456789 * 100位
 

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

修改 - 工作C code：

 长INT I，J;
    长整型* M [2];
    M [0] =（长整型*）malloc的（的sizeof（长整型）*（W + 1））;
    米[1] =（长整型*）malloc的（的sizeof（长整型）*（W + 1））;
    对于（i = 0; I＆LT; = W;我++）{
        米[0] [I] = 0;
    }

    INT读= 0;
    INT写= 1;
    INT TMP;

    长整型百分比=（W + 1）*（N）/ 100;
    长整型计数器= 0;

    对于（i = 1; I＆LT; = N;我++）{
        为（J = 0; J＆LT; = W; J ++）{
            如果（瓦特[I-1] = j）条{
                M [写入] [J] = MAX（M [阅读] [J]，（V [I-1）+ M [阅读] [J-（W [I-1]）]）;
            }其他{
                M [写入] [J] = M [阅读] [J]。
            }
            反++;
            如果（计数器==百分比）{
                输出（。）; //打印点（。），每百分数
                fflush（标准输出）;
                计数器= 0;
            }
        }
        TMP =读取;
        读=写;
        写= TMP;
    }

    的printf（\ N％LD \ N，M [阅读] [W]）;

    免费（M [0]）;
    免费（M [1]）;
 

解决方案

背包问题可以通过使用 0（W）的空间来解决。
在迭代的每一步，你只需要2行 - 阵列的当前状态 M [] 和 M [+ 1] 。

 电流= 1
INT米[2] [W]
设置为NONE M＃这意味着我们无法处理这种情况下的所有元素
M [0] [0] = 0＃这是我们的起点，初始为空背包

因为我在[1..1]做
    接下来= 3  - 电流; ///只使用1或2基于当前指数
    对于j在[0 ... W]做
       M [下一页] [J] = M [当前] [J]。
    对于j在[W [I] ... W]做
       如果m [当前] [J  -  W [我]不无则＃过程只到达位置
           M [下一页] [J] = MAX（M [下一页] [J]，M [电流] [J  -  W [I]] + V [I]）;
    电流=下一个; ///交换当前状态和产生的1
 

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

 因为我在[1..1]做
    对于j在[W [I] ... W]做
       M [J] = MAX（M [J]，男[J  -  W [I]] + V [I]）;
 

According to Wikipedia and other sources I had went through, you need matrix m[n][W]; n - number of items and W - total capacity of knapsack. This matrix get really big, sometimes too big to handle it in C program. I know that dynamic programming is based on saving time for memory but still, is there any solution where can you save time and memory?

Pseudo-code for Knapsack problem:

// 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

Lets say, that W = 123456789 and n = 100. In this case we get really big matrix m[100][123456789]. I was thinking how to implement this, but best I have in my mind is just to save which items was selected with one bit (0/1). Is this possible? Or is there any other approach for this problem?

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

I hope this is not stupid question and thanks for your effort.

EDIT - working C code:

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

解决方案

Knapsack problem can be solved using O(W) space.
At each step of the iteration you need only 2 rows - current state of the array m[i] and 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

Also it is possible to use only 1 array. Here is the pseudocode

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

这篇关于背包 - 节省时间和内存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！