背包问题

作者: RobotBerry | 来源:发表于2017-04-24 14:36 被阅读54次

    01背包

    有一个背包,最大负重为W;有n块宝石,每件宝石的价值为vi,重量为wi,i为[1,n]。求背包能装下的宝石的最大价值。

    典型的动态规划问题。状态表为dp[i][j],i为[0,n],表示宝石的下标;j为[0,W],表示递增的总负重。其状态转移方程为:

    dp[i,j] = dp[i-1][j], j < w[i];
    dp[i,j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]), j >= w[i].

    note: dp被初始化为全0数组。

    代码

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (j < w[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }
    

    由于状态转移方程只用到了相邻行的状态,因此可以把状态表缩减成一维dp[j]。此时的状态转移方程为:

    dp[j] = max(dp[j], dp[j-w[i]] + v[i]), j >= w[i]

    note: j从W递减为1

    代码

    for (int i = 1; i <= N; i++)
    {
        for (int j = W; j >= w[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    

    完全背包

    有一个背包,最大负重为W;有n种宝石,每种宝石的价值为vi,重量为wi,i为[1,n]。宝石的数量无限。求背包能装下的宝石的最大价值。

    状态表为dp[j],状态方程也是:

    dp[j] = max(dp[j], dp[j-w[i]] + v[i]), j >= w[i]

    但是j是从1递增至W,和上面的01背包相反。原因在于每种的宝石的数量都是无限的,是在解决当前问题(i种物品),向有i种物品的背包添加第i种物品;而01背包问题是在解决当前问题(i种物品),向有i-1种物品的背包添加第i种物品。

    代码

    for (int i = 1; i <= N; i++)
    {
        for (int j = w[i]; j <= W; j++)
        {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    

    多维背包

    有一个背包,最多能被Wa克a物质和Wb克b物质;有n种宝石,每种宝石的价值为vi,所含ab物质的质量分别为wai克和wbi克。求背包能装下的宝石的最大价值。

    状态表为dp[j][k],状态方程为:

    dp[j][k]=max(dp[j][k], dp[[j-wa[i]][[k-wb[i]] + vi)

    for (int i = 1; i <= N; i++)
    {
        for (int j = Wa; j >= wa[i]; j--)
        {
            for (int k = Wb; k >= wb[i]; k--)
            {
                dp[j][k] = max(dp[j][k], dp[j - wa[i]][k - wb[i]] + v[i]);
            }
        }
    }
    

    可以扩展至任意维。

    for (int i = 1; i <= N; i++)
    {
        for (int j = Wj; j >= wj[i]; j--)
        {
            for (int k = Wk; k >= wk[i]; k--)
            {
                for (int l = Wl; l >= wl[i]; l--)
                {
                    ...
                        dp[j][k][l]... = max(dp[j][k][l]..., dp[j - wj[i]][k - wk[i]][l - wl[i]]... + v[i]);
                }
            }
        }
    }
    

    相关文章

      网友评论

        本文标题:背包问题

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