背包问题 -- 二维数组写法及特殊情况01背包

93 阅读 0 评论 62 点赞

我是靠谱客的博主优美抽屉，最近开发中收集的这篇文章主要介绍背包问题 -- 二维数组写法及特殊情况01背包，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

01背包问题

有n个重量和价值分别为wi、vi的物品，每件物品都有1个。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
限制条件：
1 <= n <= 100
1 <= wi, vi <= 100
1 <= W <= 10000

具体叙述见前博客01背包。
这里要说的是dp数组是一个二维数组，不需要考虑倒序还是正序放入的问题。

先给出代码：

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

i是考虑第i件物品，j是考虑背包容量，dp的值是考虑对应的价值。

对于不同的j时每个第i+1件物品考虑放入的时候，要看第i件物品放入的时候的情况。这样不会出现重复放入相同物品的问题。

完全背包

有n个重量和价值分别为wi、vi的物品，每件物品都有n个。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
限制条件：
1 <= n <= 100
1 <= wi, vi <= 100
1 <= W <= 10000

对于这个题我结合一维滚动数组的方法，当自身可以重复放入的时候我把i+1相同情况下去和之前的j做计算。

代码如下：

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

特殊的01背包

有n个重量和价值分别为wi、vi的物品，每件物品都有1个。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
限制条件：
1 <= n <= 100
1 <= wi <= 10^7
1 <= vi <= 100
1 <= W <= 10^9

这个问题和最初的01背包相比只是修改了限制条件的大小，但是此前的方法可能会导致超时（呃，大概是一定会），那么我们试试对DP对象改动。
新的定义dp[i+1][j]是前i个物品中挑出价值总和为j时总质量的最小值（不存在就赋值INF）。
前0个物品什么都挑选不了，初始值dp[0][0] = dp[0][j] = INF;

递推式：dp[i+1][j] = min{dp[i][j], dp[i][j - v[i]]+w[i]};

最后只需要看dp[i+1]这一维度dp[i+1][j]值存在的最大j就是价值总和最大。

代码如下：

dp[0][0] = 0;
for(int i = 0; i < n; i++)
{
    for(int j = 0; j <= N*MAX_V; j++)
    {
        if(j < v[i])
        {
            dp[i+1][j] = dp[i][j];
        }
        else
        {
            dp[i+1][j] = min{dp[i][j], dp[i][j-v[i]]+w[i]};
        }
    }
}
for(int i = 0; i <= N*MAX_V; i++)
    if(dp[n][i] <= W)
        ans = i;