dp---背包

作者: 哟破赛呦 | 来源:发表于2019-01-21 11:50 被阅读12次

    01背包

    n种物品,一个承重量为m的背包,每种物品最多只能拿一个或者不拿,且每个物品都有价值v[i]和重量w[i],问怎么拿使背包内物品价值最大。
    定义dp[i][j]表示走到第i个物品,背包重量为j时的价值。
    转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
    dp[i-1][j]表示不拿当前物品,背包重量为j时的价值
    dp[i-1][j-w[i]] + v[i]表示当前拿过后,背包重量为j时的价值

    for(int i=1; i<=n; i++){
        for(int j=0; j<=m; j++){
            if(j >= w[i]){//当前承重量为j时能放进
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            }else
                dp[i][j] = dp[i-1][j];
            }
        }
    }
     //dp[n][m]就是最大价值
    

    可以发现处理第i个物品时,只需要知道i-1的状态就行了。
    滚动数组优化:

    for(int i=1; i<=n; i++){
        for(int j=m; j>=w[i]; j--){//一定是从m到w[i],反了是完全背包了
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
    //dp[m]就是最大价值
    

    注意for(int j=m; j>=w[i]; j--),一定是从大到小,容量大的状态需要通过容量小的状态转移过来。如果先更新容量小的状态,就会重复计算,变成完全背包。

    完全背包

    只有一个条件跟01背包不一样,每种物品有无数个,随便拿。
    转移方程dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i]), 0 <= k*w[i] <= m
    这里k就是拿的数量。
    还是可以用滚动数组

    for(int i=1; i<=n; i++){
        for(int j=w[i]; j<=m; j++){//从w[i]到m,跟01相反
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
    //dp[m]就是最大价值
    

    先更新小的会影响大的,很巧妙的地方就是利用重复计算达到拿多个的目的。

    多重背包

    只是跟前两个背包条件不一样,现在每种物品有num[i]
    转移方程dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i]), 0 <= k <= num[i] 且 k*w[i] <= m
    跟完全背包差不多。
    使用滚动数组:

    void _01(int w, int v, int m){//01背包,
        for(int i=m; i>=w; i--){
            dp[i] = max(dp[i], dp[i-w] + v);
        }
    }
    void _all(int w, int v, int m){//完全背包
        for(int i=w; i<=m; i++){
            dp[i] = max(dp[i], dp[i-w] + v);
        }
    }
    //利用上面两个函数,多重背包如下
    for(int i=1; i<=n; i++){//遍历每种物品
        if(num[i]*w[i] > m){
            //背包装不下所有当前物品,就可以看做完全背包
            _all(w[i], v[i], m);
        }else{
            //装的下就进行多次01背包
            //如果num[i] = 10
            //每次拿 1 2 4 3 个
            //这里相当于拿了10轮,这么处理更快
            int k=1;
            while(k<num[i]){
                _01(k*w[i], k*v[i], m);
                num[i] -= k;
                k <<= 1;
            }
            _01(num[i]*w[i], num[i]*v[i], m);
        }
    }
    //dp[m]就是结果
    

    总结

    三种背包都不算难,不用滚动数组更好理解,不需要用滚动数组的时候直接套转移方程正常dp就行。

    相关文章

      网友评论

        本文标题:dp---背包

        本文链接:https://www.haomeiwen.com/subject/vbgqjqtx.html