动态规划之背包问题（修建中）

动态规划之背包问题（修建中） 背包问题

文章目录

一、01背包问题

题目概述：题解：优化：恰好塞满体积为V的背包：练习：题解：优化： 二、完全背包问题

题目概述：题解：优化：恰好塞满体积为V的背包：练习：题解： 三、多重背包问题

题目概述：纯暴力算法题解：空间复杂度优化：时间复杂度优化1：二进制优化方法时间复杂度优化2：单调队列优化方法 四、混合背包问题五、二维费用的背包问题六、分组背包问题七、背包问题求方案数八、求背包问题的方案九、有依赖条件的背包问题参考文献

一、01背包问题

  每个物品只有选和不选，每个物品只能选1次

题目概述：

  题目链接：01背包问题

题解：

  f(i,j)表示只看前i个物品，总体积是j的情况下的最大价值。我们的答案就是max{f(n,k),k=0~v}.

  1 不选第i个物品，此时f(i,j)=f(i-1,j);

  2 选第i个物品，此时f(i,j) = f(i-1,j-v[i])+w[i];

  f(i,j)=max{1.,2.};,初始条件f(0,0) = 0;//一个都不选此时体积是0，所以价值是0

  时间复杂度：状态是N*V,状态转移是O(1)的，故时间复杂度是O(N*V)的，看一下数据范围,N*V=1000000,对比一下下表我们的算法是够用的：

  空间复杂度sizeof(int)*N*V=4*1000000 bit约等于4MB,C/C++一般是给64MB，完全ok。C++的一秒内大概可以测107~108次，也是ok的。

  背包问题是满足最优子结构，所以可以使用动态规划，证明如下：
背 包 问 题 可 以 表 示 为 : m a x ( ∑ i = 1 N w i x i ) s . t . ∑ i = 1 N v i x i < = V 设 y 1 , y 2 , . . . , y n 是 原 问 题 的 最 优 解 ， 那 么 y 1 , y 2 , . . . , y n − 1 必 然 是 子 问 题 m a x ( ∑ i = 1 N − 1 w i x i ) s . t . ∑ i = 1 N − 1 v i x i < = V − w N y N 证 明 ： 采 用 反 证 法 ， 设 存 在 一 组 解 z 1 , z 2 , . . . , z N − 1 是 上 面 子 问 题 的 最 优 解 那 么 ∑ i = 1 N − 1 w i z i > = ∑ i = 1 N − 1 w i y i 且 ∑ i = 1 N − 1 v i z i < = V − w N y N 那 么 发 现 ∑ i = 1 N − 1 w i z i + w N y N > = ∑ i = 1 N w i y i 且 ∑ i = 1 N − 1 v i z i + w N y N < = V 这 不 就 说 明 z 1 , z 2 , . . . , z N − 1 , y N 才 是 原 问 题 的 最 优 解 嘛 ， 这 与 题 意 矛 盾 所 以 原 问 题 得 证 明 。 背包问题可以表示为:\ max(sum_{i=1}^{N}{w_ix_i})\ s.t. sum_{i=1}^{N}{v_ix_i}<=V\ 设y_1,y_2,...,y_n是原问题的最优解，那么y_1,y_2,...,y_{n-1}必然是子问题\ max(sum_{i=1}^{N-1}{w_ix_i})\ s.t. sum_{i=1}^{N-1}{v_ix_i}<=V-w_Ny_N\ 证明：采用反证法，设存在一组解z_1,z_2,...,z_{N-1}是上面子问题的最优解\ 那么sum_{i=1}^{N-1}{w_iz_i}>=sum_{i=1}^{N-1}{w_iy_i}且sum_{i=1}^{N-1}{v_iz_i}<=V-w_Ny_N\ 那么发现sum_{i=1}^{N-1}{w_iz_i}+w_Ny_N>=sum_{i=1}^{N}{w_iy_i}且sum_{i=1}^{N-1}{v_iz_i}+w_Ny_N<=V\ 这不就说明z_1,z_2,...,z_{N-1},y_N才是原问题的最优解嘛，这与题意矛盾\ 所以原问题得证明。 背包问题可以表示为:max(i=1∑N​wi​xi​)s.t.i=1∑N​vi​xi​<=V设y1​,y2​,...,yn​是原问题的最优解，那么y1​,y2​,...,yn−1​必然是子问题max(i=1∑N−1​wi​xi​)s.t.i=1∑N−1​vi​xi​<=V−wN​yN​证明：采用反证法，设存在一组解z1​,z2​,...,zN−1​是上面子问题的最优解那么i=1∑N−1​wi​zi​>=i=1∑N−1​wi​yi​且i=1∑N−1​vi​zi​<=V−wN​yN​那么发现i=1∑N−1​wi​zi​+wN​yN​>=i=1∑N​wi​yi​且i=1∑N−1​vi​zi​+wN​yN​<=V这不就说明z1​,z2​,...,zN−1​,yN​才是原问题的最优解嘛，这与题意矛盾所以原问题得证明。
  所以这个问题的子结构都是最优的，可以用动态规划，代码如下：

#include 
#include 
using namespace std;
#define NUM 1001
int main()
{
    int N;
    int V;
    cin >> N >> V;
    //dp[i][j]表示只考虑下标为前i个物品选与不选，体积是j时，这些物品的最大价值
    //考虑第i个物品，要么不选择它 此时的价值就等于dp[i - 1][j]
    //如果选择它 价值就是dp[i - 1][j - v[i]] + w[i]
    //dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
    //dp[0][0] = 0;
    vector> dp(N + 1,vector(V + 1));
    //一开始默认全初始化成0也有表明什么都不放是一个合理解的理由
    int v[NUM], w[NUM];
    //v[i]表示第i件物品的体积
    //w[i]表示第i件物品的价值
    for (int i = 1; i <= N; ++i)
    {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 0; j <= V; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if (j - v[i] >= 0)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    int ret = 0;
    for (int j = 0; j <= V; ++j)
    {
        ret = max(ret, dp[N][j]);
    }
    cout << ret << endl;
    return 0;
}

优化：

  注意到本题可以用滚动数组优化如下：

#include 
#include 
using namespace std;


int main()
{
    int N,V;
    cin >> N >> V;
    vector v(N + 1);
    vector w(N + 1);
    for (int i = 1; i <= N; ++i)
    {
        //v[i]表示第i个物品的体积
        //w[i]表示第i个物品的价格
        cin >> v[i] >> w[i];
    }
    //观察状态转移方程：
    //f(i,j) = max(f(i-1,j), f(i-1,j-v[i]) + w[i])
    //只和前一行有关
    //可以用滚动数组优化
    vector dp(V + 1);
    for (int i = 1; i <= N; ++i)
    {
        //我们注意到 我们要的上一行的状态是f(i-1,j)和f(i-1, j - v[i])
        //前一个还好说，肯定通过正向遍历上一轮计算过了 在f[j]里头
        //但是如果正常0~j遍历 必然会把f(i - 1, j - v[i])更新掉
        //所以我们就内层循环反方向循环
        //这样f(i-1,j-v[i])一定还没更新过 是上一层i-1里头的
        //并且保证j-v[i]大于0
        for (int j = V; j >= v[i]; --j)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    //dp[V]一定是最优解了，因为出现了最优解后会一层一层转移到最后
    cout << dp[V] << endl;
    return 0;
}

恰好塞满体积为V的背包：

  状态转移方程一致，所以需要修改的只有初始条件；

  恰好塞满要初始化成dp[i][j] = INT_MIN(一位数组则为f[j]);(如果是最小效用就初始化成INT_MAX),这表明刚开始的时候恰好塞满体积为j的背包没有合理的解，不过dp[i][0]仍然要赋0表明填满体积为0的背包的最大价值是0，最后在输出时，如果dp[N][V]==INT_MIN,说明本题无合理解，输出无解即可。

练习：

LeetCode416. 分割等和子集

题解：

class Solution {
public:
    bool canPartition(vector& nums) 
    {
        int sum = 0;
        int maxelem = INT_MIN;
        for (auto e : nums)
        {
            maxelem = max(maxelem, e);
            sum += e;
        }
        if (sum % 2 != 0)
        {
            return false;
        }
        
        int N = nums.size();
        if (N < 2)
        {
            return false;
        }
        int V = sum / 2;
        if (V < maxelem)
        {
            return false;
        }
        vector> f(N, vector(V + 1));
        for (int i = 0; i < N; ++i)
        {
            f[i][0] = true;
        }
        f[0][nums[0]] = true; 
        for (int i = 1; i < N; ++i)
        {
            for (int j = 0; j <= V; ++j)
            {
                if (nums[i] <= j)
                {
                    f[i][j] = f[i - 1][j] || f[i - 1][j - nums[i]];
                }
                else
                {
                    f[i][j] = f[i - 1][j];
                }
            }
        }
        return f[N - 1][V];
    }
};

优化：

class Solution {
public:
    bool canPartition(vector& nums) 
    {
        int N = nums.size();
        int maxelem = INT_MIN;
        int sum = 0;
        for (auto e : nums)
        {
            sum += e;
            if (maxelem < e)
            {
                maxelem = e;
            }
        }
        //sum如果是奇数 必定无法分成等和子集
        if (sum & 1 != 0)
        {
            return false;
        }
        int V = sum / 2;
        //如果最大元素比我们要装满的背包体积大
        //那也是不能分成两个等和子集的
        if (V < maxelem)
        {
            return false;
        }
        //转化为恰好装满一个体积为V的背包
        
        vector f(V + 1);
        f[0] = true;
        f[nums[0]] = true;
        for (int i = 1; i < N; ++i)
        {
            for (int j = V; j >= 1; --j)
            {
                if (j - nums[i] >= 0)
                {
                    //从大数开始遍历的目的是保证f[j - nums[i]]是上一轮计算的f[i - 1][j - nums[i]]
                    f[j] = f[j] || f[j - nums[i]];
                }
            }
        }
        return f[V];
    }
};

二、完全背包问题 题目概述：

题目链接：完全背包问题

题解：

  定义状态f(i,j)只考虑前i个表示总体积不超过j时的最大价值，仔细想一想，这里是完全背包问题，所以状态转移时，我们可以考虑不选第i个物品的价值或者选1个第i个物品，选两个第i个物品…选k个第i个物品(k*w[i] <= j)，所以状态转移方程应该如下：
f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i − 1 , j − v [ i ] ) + w [ i ] , f ( i − 1 , j − 2 ∗ v [ i ] ) + 2 ∗ w [ i ] , . . . , f ( i − 1 , j − k ∗ v [ i ] ) + k ∗ w [ i ] ) , s . t . j − k ∗ v [ i ] > = 0 f(i,j) = max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2*v[i])+2*w[i],...,f(i-1,j-k*v[i])+k*w[i]),\ s.t.j-k*v[i]>=0\ f(i,j)=max(f(i−1,j),f(i−1,j−v[i])+w[i],f(i−1,j−2∗v[i])+2∗w[i],...,f(i−1,j−k∗v[i])+k∗w[i]),s.t.j−k∗v[i]>=0
  实现这个状态转义方程的朴素代码应该是：

#include 
#include 
using namespace std;

int main()
{
    int N,V;
    cin >> N >> V;
    vector v(N + 1);
    vector w(N + 1);
    for (int i = 1; i <= N; ++i)
    {
        cin >> v[i] >> w[i];
    }
    vector> f(N + 1, vector(V + 1));
    
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 0; j <= V; ++j)
        {
            for (int k = 0; k * v[i] <= j; ++k)
            {
                //这里k等于0时就包含了f[i - 1][j]
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }
    cout << f[N][V] << endl;
    return 0;
}

  运行一下，发现：

  因为我们这个时间复杂度超过了O(N*V),时间复杂度变成了O(N*V*V).要想办法优化。

  注意到：
f ( i , j − v [ i ] ) = m a x ( f ( i − 1 , j − v [ i ] ) , f ( i − 1 , j − 2 ∗ v [ i ] ) + 1 ∗ w [ i ] , . . . f ( i − 1 , j − k ∗ v [ i ] ) + ( k − 1 ) ∗ w [ i ] ) s . t . k = 1 , 2 , 3 , . . . j − k ∗ w [ i ] > = 0 f(i,j-v[i]) = max(f(i-1,j-v[i]),f(i-1,j-2*v[i])+1*w[i],...f(i-1,j-k*v[i])+(k-1)*w[i])\ s.t.k = 1,2,3,...j-k*w[i]>=0\ f(i,j−v[i])=max(f(i−1,j−v[i]),f(i−1,j−2∗v[i])+1∗w[i],...f(i−1,j−k∗v[i])+(k−1)∗w[i])s.t.k=1,2,3,...j−k∗w[i]>=0
  再与原本的状态转义方程对比：
f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i − 1 , j − v [ i ] ) + w [ i ] , f ( i − 1 , j − 2 ∗ v [ i ] ) + 2 ∗ w [ i ] , . . . , f ( i − 1 , j − k ∗ v [ i ] ) + k ∗ w [ i ] ) , s . t . j − k ∗ v [ i ] > = 0 f(i,j) = max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2*v[i])+2*w[i],...,f(i-1,j-k*v[i])+k*w[i]),\ s.t.j-k*v[i]>=0\ f(i,j)=max(f(i−1,j),f(i−1,j−v[i])+w[i],f(i−1,j−2∗v[i])+2∗w[i],...,f(i−1,j−k∗v[i])+k∗w[i]),s.t.j−k∗v[i]>=0
  发现两式可以结合为：
f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i , j − v [ i ] ) + w [ i ] ) f(i,j)=max(f(i-1,j),f(i,j-v[i])+w[i]) f(i,j)=max(f(i−1,j),f(i,j−v[i])+w[i])
  我们得到了新的状态转移方程！这个方程转移的 *** 作显然是O(1)的，这样时间复杂度就优化到了O(N*V);

#include 
#include 
using namespace std;

int main()
{
    int N, V;
    cin >> N >> V;
    vector v(N + 1);
    vector w(N + 1);
    for (int i = 1; i <= N; ++i)
    {
        cin >> v[i] >> w[i];
    }
    vector> f(N + 1, vector(V + 1));
    
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 0; j <= V; ++j)
        {
            f[i][j] = f[i - 1][j];
            if (j - v[i] >= 0)
            {
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
            }
        }
    }
    cout << f[N][V] << endl;
    return 0;
}

优化：

  同理，使用滚动数组优化空间复杂度到O(V).这里要注意的是状态转移方程中：
f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i , j − v [ i ] ) + w [ i ] ) f(i,j) = max(f(i - 1,j),f(i,j-v[i]) + w[i]) f(i,j)=max(f(i−1,j),f(i,j−v[i])+w[i])
  后一个是i开头的，所以必须是本行计算过的数据，所以内层循环要从小到大算，而不是像0-1背包问题一样从大往小算。

#include 
#include 
using namespace std;

int main()
{
    int N, V;
    cin >> N >> V;
    vector f(V + 1);
    int v, w;
    for (int i = 1; i <= N; ++i)
    {
        
        cin >> v >> w;
        for (int j = 0; j <= V; ++j)
        {
            
            if (j >= v)
            {
                f[j] = max(f[j], f[j - v] + w);
            }
        }
    }
    cout << f[V] << endl;
    return 0;
}

恰好塞满体积为V的背包：

  如果题目问的是恰好塞满V体积的背包，首先发现状态转移方程是一致的，那么需要修改的只有初始条件。

  那么在初始化时只要把f(m)二维数组则为f[i][j],m!=0初始化成INT_MIN(如果是最小效用就初始化成INT_MAX),表明一开始是没有合理解的就可以了，不过f(0)仍然要初始化成0，因为组成0体积的背包的最大效用确实是0，没法装东西。最后输出是，注意检查一下f(V)是否等于INT_MIN来check是否有合理解。

练习：

LeetCode322. 零钱兑换

题解：

  本题可以视为一个完全背包问题的变种，第i个物品的体积是coins[i - 1],价值是1，恰好塞满一个体积为amount的背包，所需的最小价值。

  定义f(i,j)为前i个元素塞满空间为j的背包所需的最小价值数，显然f(i,0) = 0;，其他均初始化成INT_MAX表示此时还没有合法解。

  这个价值为1的完全背包问题的状态转移方程为：
f ( i , j ) = m i n ( f ( i − 1 , j ) , f ( i , j − c o i n s [ i − 1 ] ) + 1 ) f(i,j) = min(f(i-1,j), f(i,j-coins[i-1])+1) f(i,j)=min(f(i−1,j),f(i,j−coins[i−1])+1)
  所以代码如下：

class Solution {
public:
    int coinChange(vector& coins, int amount) 
    {
        
        int size = coins.size();
        vector> dp(size + 1, vector(amount + 1, INT_MAX));
        for (int i = 0; i <= size; ++i)
        {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= size; ++i)
        {
            for (int j = 1; j <= amount; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (j - coins[i - 1] >= 0)
                {
                    
                    if (dp[i][j] - 1 > dp[i][j - coins[i - 1]])
                    {
                        dp[i][j] = dp[i][j - coins[i - 1]] + 1;
                    }
                }
            }
        }
        //如果dp[size][amount] == INT_MAX表明没有合法解 返回-1
        return dp[size][amount] == INT_MAX ? -1 : dp[size][amount];
    }
};

  优化空间复杂度：

class Solution {
public:
    int coinChange(vector& coins, int amount) 
    {
        
        int size = coins.size();
        vector dp(amount + 1, INT_MAX);
        
        dp[0] = 0;//组成体积为0的背包显然是不需要任何硬币就可以组成的
        for (int i = 1; i <= size; ++i)
        {
            for (int j = coins[i - 1]; j <= amount; ++j)
            {
                
                if (dp[j] - 1 > dp[j - coins[i - 1]])
                {
                    dp[j] = dp[j - coins[i - 1]] + 1;
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

  总之，完全背包为题和0-1背包问题的区别仅在状态转义方程，如果是恰好塞满注意初始化时的条件改一改。

三、多重背包问题 题目概述：

链接：多重背包问题1

分析：数据范围是100，我们可以用O(N^3)的算法解决。显然本题就是一个简化版的完全背包问题，按照完全背包问题的状态转移方程不要化简就可以了，选0个i，选1个i，选2个i，…，选k个is.t.k*v[i] <= j && k <= w[i].

纯暴力算法题解：

#include 
#include 
using namespace std;

int main()
{
    int N, V;
    cin >> N >> V;
    vector v(N + 1);//第i个物品的体积v[i]
    vector w(N + 1);//第i个物品的价值w[i]
    vector s(N + 1);//第i个物品的最大选择个数s[i]
    for (int i = 1; i <= N; ++i)
    {
        cin >> v[i] >> w[i] >> s[i];
    }
    vector> dp(N + 1, vector(V + 1));
    
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 0; j <= V; ++j)
        {
            for (int k = 0; k * v[i] <= j && k <= s[i]; ++k)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}

空间复杂度优化：

  同理，这个动态规划状态转移方程可以用滚动数组反向遍历优化：

#include 
#include 
using namespace std;

int main()
{
    int N, V;
    cin >> N >> V;
    int v, w, s;
    vector dp(V + 1);
    for (int i = 1; i <= N; ++i)
    {
        cin >> v >> w >> s;
        for (int j = V; j >= 0; --j)
        {
            for (int k = 1; k * v <= j && k <= s; ++k)
            {
                
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

时间复杂度：O(N * V * V/w)

空间复杂度：O(V)

时间复杂度优化1：二进制优化方法

多重背包问题II

  本题的数据范围扩大到了1000 2000,如果再用O(N V V /w)的算法，运算次数会到达10^9，会超掉。

  考虑如何把这个多重背包问题化简为0-1背包问题，首先想到的思路是每个物品不是可以选s[i]份嘛，那我把每个物品都拆开，这样不就变成了选与不选的0-1背包问题了嘛，但是这样时间复杂度也会超掉，本题s[i] <= 2000,2000 * 2000 * 1000 一样是10^9级别的。

  更为简洁的拆法是采用二进制的拆法，比如7，要求拆成最少数目的小于7的几个数，使得小于7的所有数都可以由这些数组合出来。

  0~7有8个方案，采用二进制的考虑方法， 0 0 0，三个位置分别选择填1或者不填入1，这样就转化为1是否选、2是否选、4是否选，这样3个数就能表达8个方案。

  把这个问题做一下转化，一个大小为s的数，最少拆为多少个数使得这些数能够表达0~s的所有数？

  答案是[log2s] + 1,以10为例即可，10实际需要4个数，但是1 2 4 8都能表达0~15的数了，显然表达范围太广了，所以实际上可以让最后一个数一直减小，直到这四个数的和是10,1 2 4 3.

  为什么这样就能表示出0~10的所有数呢？首先，我们选择 1 2 4可以表示出的数是 07，再加上一个数3可以表示出来的数就是010咯。

  所以凑s，选出log2s的那些数，最后一个数变为s-1-2-4-8-…，前面的数能凑出的范围是0~2^([log2s]),然后再补上最后一个数就能表示0~s的所有数了，且因为总和才刚到s，所以不会溢出。

  把这种思想带入这个转化为0-1背包的过程，对于每个物品，拆分并非s份，而是log2s的级别份.

  测一下时间复杂度，1000 * 2000 * log2 2000 = 2000 000 * 11是2kw级别的。

  所以我们先要把每个物品按照1 2 4 8 。。。分割，然后转化为0 - 1背包问题，代码如下：

#include 
#include 
using namespace std;


struct good
{
    int v;
    int w;
};

int main()
{
    int N, V;
    cin >> N >> V;
    vector goods;
    int v, w, s;
    
    for (int i = 0; i < N ; ++i)
    {
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k *= 2)
        {
            s -= k;
            goods.push_back({v * k, w * k});
        }
        
        if (s > 0)
        {
            goods.push_back({v * s, w * s});
        }
    }
    vector f(V + 1);
    
    for (auto e : goods)
    {
        for (int j = V; j >= e.v; --j)
        {
            f[j] = max(f[j], f[j - e.v] + e.w);
        }
    }
    cout << f[V] << endl;
    return 0;
}

时间复杂度优化到了O(N*logs*V);

  然而还能优化：

时间复杂度优化2：单调队列优化方法

  此时的数据范围如果还使用刚刚的算法，1000* log(20000) * 20000 = 1000 * 20000 * 14 = 3 * 10^8，已经接近上限了，很有可能不过。

  我们希望能把这个题优化到O(N*V)

四、混合背包问题 五、二维费用的背包问题 六、分组背包问题

  分成很多组，每组只能选一件，组内物品是互斥的。

七、背包问题求方案数 八、求背包问题的方案 九、有依赖条件的背包问题

  选一个物品必须要选它的依赖物品。

参考文献

背包问题9讲专题喵の编程课3：动态规划 01背包ACWing 3.完全背包问题 作者Chareles由数据范围反推算法复杂度以及算法内容 作者yxc动态规划之背包问题系列 作者SMONdd大牛的背包9讲