动态规划背包问题算法说明

图标

豆瓜

豆瓜网

豆瓜网专栏

首发
豆瓜 图标 2020-07-24 11:42:37

0-1背包

题目:有一个容量为 V 的背包,和一些物品。这些物品分别有两个属性,体积 w 和价值 v,每种物品只有一个。要求用这个背包装下价值尽可能多的物品,求该最大价值,背包可以不被装满。 

0-1背包问题:在最优解中,每个物品只有两种可能的情况,即在背包中或者不在背包中(背包中的该物品数为0或1),因此称为0-1背包问题。

步骤1-找子问题:子问题必然是和物品有关的,对于每一个物品,有两种结果:能装下或者不能装下。第一,包的容量比物品体积小,装不下,这时的最大价值和前i-1个物品的最大价值是一样的。第二,还有足够的容量装下该物品,但是装了不一定大于当前相同体积的最优价值,所以要进行比较。由上述分析,子问题中物品数和背包容量都应当作为变量。因此子问题确定为背包容量为j时,求前i个物品所能达到最大价值。

步骤2-确定状态:由上述分析,“状态”对应的“值”即为背包容量为j时,求前i个物品所能达到最大价值,设为dp[i][j]。初始时,dp[0][j](0<=j<=V)为0,没有物品也就没有价值。

步骤3-确定状态转移方程:由上述分析,第i个物品的体积为w,价值为v,则状态转移方程为

  • j<w,dp[i][j] = dp[i-1][j] //背包装不下该物品,最大价值不变

  • j>=w, dp[i][j] = max{ dp[i-1][j-list[i].w] + v, dp[i-1][j] } //和不放入该物品时同样达到该体积的最大价值比较

示例代码(具体输入输出见王道机试指南第七章):

复制代码

#include<cstdio>int max(int a, int b)//取最大值函数{    return a > b ? a : b;
}struct Thing
{    int w;    int v;
}list[101];int dp[101][1001];int main()
{    int s, n;//背包容量和物品总数
    while (scanf("%d%d", &s, &n) != EOF)
    {        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", &list[i].w, &list[i].v);//读入每个物品的体积和价值        }        for (int i = 0; i <= s; i++) dp[0][i] = 0;//初始化二维数组
        for (int i = 1; i <= n; i++)//循环每个物品,执行状态转移方程        {            for (int j = s; j >= list[i].w; j--)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - list[i].w] + list[i].v);
            }            for (int j = list[i].w - 1; j >= 0; j --)
            {                dp[i][j] = dp[i - 1][j];
            }
        }
        printf("%d\n", dp[n][s]);
    }    return 0;
}

复制代码

直接按照状态转移方程正序遍历j也可以,上方代码只是为了和优化算法统一。

正序遍历j示例代码

变式:要求恰好装满背包时,把dp[0][0]设为0,其余dp[0][i]设为负无穷即可,这样只有恰好达到dp[n][s]时,dp[n][s]才为正值(用优化算法也可以)。

变式示例代码

优化算法:

观察状态转移方程的特点,我们发现dp[i][j]的转移只与dp[i-1][j-list[i].w]和dp[i-1][j]有关,即仅与二维数组本行的上一行有关。因此,我们可以将二维数组优化为一维数组。不过这里要注意两点:1.j<w的状态转移方程不再需要了。2.为保证每个物品只能使用一次,我们倒序遍历所有j的值,这样在更新dp[j]的时候,dp[j-list[i].w]的值尚未被修改,就不会出现一个物品重复使用的问题。

优化后的状态转移方程:dp[j] = max{ dp[j-list[i].w] + v, dp[j] }

复杂度分析:其状态数量为n*s, n为物品数量,s为背包总体积,状态转移复杂度为O(1),所以综合时间复杂度为O(n*s),优化后的空间复杂度仅为O(s)。

示例代码:

复制代码

#include<cstdio>int max(int a, int b)//取最大值函数{    return a > b ? a : b;
}struct Thing
{    int w;    int v;
}list[101];int dp[1001];int main()
{    int s, n;//背包容量和物品总数
    while (scanf("%d%d", &s, &n) != EOF)
    {        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", &list[i].w, &list[i].v);//读入每个物品的体积和价值        }        for (int i = 0; i <= s; i++) dp[i] = 0;//初始化二维数组
        for (int i = 1; i <= n; i++)//循环每个物品,逆序遍历j执行状态转移方程        {            for (int j = s; j >= list[i].w; j--)
            {
                dp[j] = max(dp[j], dp[j - list[i].w] + list[i].v);
            }
        }
        printf("%d\n", dp[s]);
    }    return 0;
}

复制代码

完全背包

我们扩展0-1背包问题,使每种物品的数量无限增加,便得到完全背包问题:有一个容积为 V 的背包,同时有 n 个物品,每个物品均有各自的体积 w 和价值 v,每个物品的数量均为无限个,求使用该背包最多能装的物品价值总和。

正好利用了上述0-1背包的优化算法,这时我们正序遍历j,正好可以实现每种物品的重复利用,即相当于每种物品有无限个。

完全背包示例代码

完全背包例题:POJ1384 Piggy-Bank

Piggy-bank AC代码

多重背包

多重背包问题介于 0-1 背包和完全背包之间:有容积为V的背包,给定一些物品,每种物品包含体积 w、价值 v、和数量 k,求用该背包能装下的最大价值总量。

与之前讨论的问题一样,我们可以将多重背包问题直接转化到 0-1 背包上去,即每种物品均被视为k种不同物品,对所有的物品求0-1背包。其时间复杂度为O(s*Σki)。

由此可见,降低每种物品的数量 ki 将会大大的降低其复杂度,于是我们采用一种更为有技巧性的拆分。将原数量为 k 的物品拆分为若干组,每组物品看成一件物品,其价值和重量为该组中所有物品的价值重量总和,每组物品包含的原物品个数分别为:为:1、2、4…k-2^c+1,其中 c 为使 k-2^c+1 大于 0 的最大整数。这种类似于二进制的拆分,不仅将物品数量大大降低,同时通过对这些若干个原物品组合得到新物品的不同组合,可以得到 0 到 k 之间的任意件物品的价值重量和,所以对所有这些新物品做 0-1 背包,即可得到多重背包的解。由于转化后的 0-1 背包物品数量大大降低,其时间复杂度也得到较大优化,为O(s*Σlog2(ki))。


本文由豆瓜网专栏作家 豆瓜 投稿发布,并经过豆瓜网编辑审核。

转载此文章须经作者同意,并附上出处(豆瓜网)及本页链接。

若稿件文字、图片、视频等内容侵犯了您的权益,请联系本站进行 投诉处理

图标 图标

豆瓜

豆瓜网

豆瓜网专栏

  • 动态规划背包问题算法说明

    图标
    豆瓜 图标 · 今天 11:42:37 · 0浏览
  • linux端口映射说明

    图标
    豆瓜 图标 · 今天 11:41:46 · 1浏览
  • webshell河马查杀工具

    webshell河马查杀工具

    图标
    豆瓜 图标 · 今天 11:38:13 · 11浏览
  • 全部评论

    豆瓜

    豆瓜网

    豆瓜网专栏

  • 动态规划背包问题算法说明
  • linux端口映射说明
  • webshell河马查杀工具
  • 网站木马检测工具有哪些
  • assemblyinfo文件说明
  • 我来说两句