学习了0-1背包

用auto_ptr解决内存泄露的问题

SubPixel 亚像素

Jan 8

felix021 @ 2009-1-8 17:11 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(5549) | Via 本站原创

大 | 中 | 小

其实好简单的=.= 为啥以前没去看捏。。。

已知有n个东东为u[1]~u[n], 体积和重量分别是s[1]~s[n]和w[1]~w[n]
有一个包包可以装下大小为S的东东，求这个包包最重可以装多重。
记W[n][S]为要求的东西: 从n个东东里面取出一部分填满体积为S的包包
很容易理解，W[n][S]为以下两个取值的最大值：
1. W[n-1][S] 不取第n个东东，最多可以装多重
2. (s[n] <= S的时候) w[n] + W[n-1][S-s[n]] 一定取第n个东东，重量为v[n]，包包还能装S-s[n]，那么前n-1个东东最多可以装多重。
另外，显然可以看出，当n或者S为0的时候，W[n][S]肯定也为0。
最简单的是写一个递归：

int s[10100], w[10100]; //存放s和w (注意第一个数据放在下标为1的地方哦，不是从0开始的)

int knapsack_r(int n, int S){
    if(n == 0 || S == 0) return 0;
    else {
        if(s[n] <= S)
            return max(knapsack_r(n-1, S), knapsack_r(n-1, S-s[n]) + w[n]);
        else
            return knapsack_r(n-1, S);
    }
}

但是这样效率太低，实际上中间重复计算了好多东西，用一个大数组来保存中间结果，用空间换时间，于是代码就改为：

int W[10100][10100];  //存放中间数据的数组

int knapsack_r(int n, int S){ // 递归改良版，框架没变
    if(W[n][S] >= 0) return W[n][S];
    else if(n == 0 || S == 0) {
        W[n][S] = 0;
        return 0;
    } else{
        int ans = knapsack_r(n-1, S);
        if(s[n] <= S)
           ans = max(knapsack_r(n-1, S), knapsack_r(n-1, S-s[n]) + w[n]);
        W[n][S] = ans;
        return ans;
    }
}

void knapsack(int n, int S){ //递推版，从[0][0]填到[n][S]，答案就出来拉
    int i, j;
    for(i = 0; i < n; ++i) W[i][0] = 0;
    for(i = 0; i < S; ++i) W[0][i] = 0;
    for(i = 1; i <= n; ++i){
        for (j = 1; j <= S; ++j){
            W[i][j] = W[i-1][j];
            //s, v是从0开始计数的，所以是 i-1
            if(s[i] <= j) W[i][j] = max(W[i][j], W[i-1][j-s[i]]+w[i]);
        }
    }
}

递推版需要计算所有的n * S个W，而递归版本只要计算其中的一部分(在数据小的时候可以观察矩阵得知)
看起来好像递归版本会更省时间，但是实际上不是这样的：
在数据比较大的情况下，比如n = 10000, S = 10000，递归版用了7s多，递推版才2s多(T2410 2.0GHz + 3G DDRII 533)
大概是因为：
1. 数据比较大的情况下，递归版也要计算大部分的数据，不会差太多
2. 递归过程中反复调用子程序耗费了大量的时间。

基本上，0-1背包的DP解法(还有搜索解法O(2^n))的时间复杂度就是O(nS)了，上面给出的解法空间复杂度是O(nS)
但是稍稍观察下，可以发现，在每次外层循环以后W[i-1]就没用了，所以可以把空间复杂度改进到O(S)
假设我们用一个数组W1[0..S]，那么事实上这里的W1[j]就是上一次循环计算出来的W[i-1][j]，把内层循环倒过来得到：

int W1[10100];

int knapsack1(int n, int S){
    int i, j;
    for(i = 0; i <= S; ++i) W1[i] = 0;
    for(i = 1; i <= n; ++i)
        for(j = S; j >= 1; --j)
            if(s[i] <= j) W1[j] = max(W1[j], W1[j-s[i]] + v[i]);
}

于是就得出了O(S)空间复杂度的算法了，而且效率还提高了，只要1.4s左右。
最后再加上一些小的流程优化的，比如在j < w[i]的时候就没必要循环了；在内层循环开始之前，保存s[i], v[i]：

int knapsack1(int n, int S){
    int i, j, ts, tv;
    for(i = 0; i <= S; ++i) W1[i] = 0;
    for(i = 1; i <= n; ++i)
        for(j = S, ts=s[i], tv=v[i]; j >= ts; --j)
            W1[j] = max(W1[j], W1[j-ts] + tv);
}

最后结果是被优化到了1.2s左右，还是有比较明显的效果的。

欢迎扫码关注：