背包问题 订阅
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪,早期的作品可追溯到1897年 [1]  数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品 [2]  ,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。 展开全文
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪,早期的作品可追溯到1897年 [1]  数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品 [2]  ,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
信息
外文名
Knapsack Problem
提出者
Merkle-Hellman
中文名
背包问题
应用领域
运筹学,应用数学,密码学等
背包问题应用
1998年的石溪布鲁克大学算法库的研究表明,在75个算法问题中,背包问题是第18个最受欢迎,第4个最需要解决的问题(前三为后kd树,后缀树和bin包装问题)。 [3]  背包问题出现在各种领域的现实世界的决策过程中,例如寻找最少浪费的方式来削减原材料, [4]  选择投资和投资组合, [5]  选择资产支持资产证券化 [6]  ,和生成密钥为Merkle-Hellman [7]  和其他背包密码系统。背包算法的一个早期应用是在测试的构建和评分中,测试者可以选择他们回答哪些问题。对于小例子来说,这是一个相当简单的过程,为测试者提供这样的选择。例如,如果考试包含12个问题,每个问题的价值为10分,测试者只需回答10个问题即可获得100分的最高分。然而,在点值的异质分布的测试 - 即不同的问题值得不同的点值 - 更难以提供选择。 Feuerman和Weiss提出了一个系统,其中学生被给予一个异质测试,共有125个可能的点。学生被要求尽可能回答所有的问题。在总点数加起来为100的问题的可能子集中,背包算法将确定哪个子集给每个学生最高的可能得分。 [8] 
收起全文
精华内容
下载资源
问答
  • 背包问题

    2021-07-13 14:31:40
    01背包问题本题解析AC代码代码优化AcWing 3. 完全背包问题本题解析TLE代码优化AC代码代码优化AcWing 4. 多重背包问题本题解析AC代码AcWing 5. 多重背包问题 II本题解析AC代码AcWing 9. 分组背包问题本题解析AC代码...


    前言

    复习acwing算法基础课的内容,本篇为讲解基础算法:动态规划——背包问题,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。


    一、动态规划

    动态规划(Dynamic Programming,DP)是求解决策过程最优化的过程,个人认为是目前接触的所有算法里最绕的…

    这里的题目的解题方法来自于:y总的闫氏dp分析法


    二、例题,代码

    AcWing 2. 01背包问题

    本题链接:AcWing 2. 01背包问题
    本博客提供本题截图:
    在这里插入图片描述

    本题解析

    在这里插入图片描述

    AC代码

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010;
    
    int v[N];      //体积
    int w[N];      //价值
    int f[N][N];   // f[i][j], j体积下前i个物品的最大价值 
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        
        for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j];    //不装这个第i件物品
                if (j >= v[i])            //如果可以装第i件物品
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }
            
        cout << f[n][m] << endl;
        
        return 0;
    }
    

    代码优化

    我们把二维数组转为一维数组
    这里先给出AC代码,然后去讲解其中的细节

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010;
    
    int n, m;
    int v[N], w[N];
    int f[N];
    
    int main()
    {
        cin >> n >> m;
    
        for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
        for (int i = 1; i <= n; i ++ )
            for (int j = m; j >= v[i]; j -- )
                f[j] = max(f[j], f[j - v[i]] + w[i]);
    
        cout << f[m] << endl;
    
        return 0;
    }
    

    首先去解释我们的数组f,这里的f[j]代表的是,在背包容量为j的前提下的最优解

    我们可以观察和第一个AC代码的最大差距就是对于我们的第二个for循环,我们的第二个for循环相当于是逆序的,这里来解释一下为什么是逆序:

    对于二维数组的状态 (未优化版本),我们的状态f[i][j]其实是由i - 1这个状态表达出来的,我们可以理解为:小的数据是需要我们去保护的,不能被破坏的,因为我们在优化的过程中,其实动态规划的思维是没有改变的,即该题的实现方式是没有发生改变的,我们只是用了一种更为高效的方式去优化我们的代码,故我们需要维护小的数据,即从大到小去循环遍历,保护我们的小数据,简单来说的话,就是我们如果正序遍历,我们的小数据会被【破坏】,但是我们的大数据是由小数据得到的,故我们为了防止小数据被【破坏】,我们采用逆序的遍历更新方式。

    AcWing 3. 完全背包问题

    本题链接:AcWing 3. 完全背包问题
    本博客提供本题截图:
    在这里插入图片描述

    本题解析

    在这里插入图片描述

    TLE代码

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010;
    
    int v[N], w[N];
    int f[N][N];
    
    int  main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) cin >>v[i] >> w[i];
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) 
                for (int k = 0; v[i] * k <= j; k ++ )
                    f[i][j] = max (f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                    
        cout << f[n][m] << endl;
        
        return 0;
    }
    

    优化

    在这里插入图片描述

    AC代码

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010;
    
    int v[N], w[N];
    int f[N][N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j];
                if (j >= v[i])
                	f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
            }
        
        cout << f[n][m] << endl;
        
        return 0;
    }
    

    代码优化

    有没有感觉这个代码似曾相识呢?可以回去对比一下01背包问题中的代码,我们可以惊讶的发现,完全背包问题和01背包问题的代码大致都一样,只有核心代码处有细小的差别:

    f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);         01背包
    f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);            多重背包

    所以我们可以按照01背包类似的优化方法去优化,这里注意,01背包问题中每一个f[i, j]状态都是由f[i - 1, j]得到的,这就是唯一和多重背包问题不同的地方,故我们的多重背包的优化即第二重循环为正序即可

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010;
    
    int v[N], w[N];
    int f[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
        
        for (int i = 1; i <= n; i ++ )
            for (int j = v[i]; j <= m; j ++ )
                f[j] = max(f[j], f[j - v[i]] + w[i]);
        
        cout << f[m] << endl;
        
        return 0;
    }
    

    AcWing 4. 多重背包问题

    本题链接:AcWing 4. 多重背包问题
    本博客提供本题截图:
    在这里插入图片描述

    本题解析

    本题数据小,直接暴力枚举即可

    AC代码

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 110;
    
    int f[N][N];
    int v[N], w[N], s[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
                for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
                    f[i][j] = max (f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);
                    
        cout << f[n][m] << endl;
        
        return 0;
    }
    

    AcWing 5. 多重背包问题 II

    本题链接:AcWing 5. 多重背包问题 II
    本博客提供本题截图:
    在这里插入图片描述

    本题解析

    本题和上一题基本相同,但是如果还是暴力去做的话显然会TLE,这里我们采用二进制去优化:

    比如,对于一个数1023,如果我们进行正常的枚举的话需要枚举1024次,但是如果我们把它拆成:
    1 2 4 8 16 32 64 128 256 512,这么10组数字通过组合可以组合出1~1023中所有的数字

    那么对于一个随意的数字比如200,我们也可以通过相同的方式进行拆解:
    1 2 4 8 16 32 64 128 73

    按照上述操作进行打包之后,我们只需要按照正常的01背包问题即可得到答案

    AC代码

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 25000, M = 2010;
    
    int v[N], w[N];
    int f[M];
    
    int main()
    {
        int n, m;
        int cnt = 0;
        cin >> n >> m;
        
        for (int i = 1; i <= n; i ++ )
        {
            int a, b, s;
            cin >> a >> b >> s;
            int k = 1;
            while (k <= s)
            {
                cnt ++;
                v[cnt] = a * k;
                w[cnt] = b * k;
                s -= k;
                k *= 2;
            }
            if (s > 0)
            {
                cnt ++;
                v[cnt] = a * s;
                w[cnt] = b * s;
            }
        }
        
        n = cnt;
        
        for (int i = 1; i <= n; i ++ )
            for (int j = m; j >= v[i]; j -- )
                f[j] = max (f[j], f[j - v[i]] + w[i]);
                
        cout << f[m] << endl;
        
        return 0;
    }
    

    AcWing 9. 分组背包问题

    本题链接:AcWing 9. 分组背包问题
    本博客提供本题截图:
    在这里插入图片描述
    在这里插入图片描述

    本题解析

    在这里插入图片描述
    这里直接发一维优化后的代码,注意到第i个状态是由i - 1状态推导而来的,故采用的是01背包问题的优化方式

    AC代码

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 110;
    
    int v[N][N], w[N][N], s[N];
    int f[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ )
        {
            cin >> s[i];
            for (int j = 0; j < s[i]; j ++ )
                cin >> v[i][j] >> w[i][j];
        }
        
        for (int i = 1; i <= n; i ++ )
            for (int j = m; j >= 1; j -- )
                for (int k = 0; k < s[i]; k ++ )
                    if (v[i][k] <= j)
                        f[j] = max (f[j], f[j - v[i][k]] + w[i][k]);
                    
        cout << f[m] << endl;
        
        return 0;
    }
    

    三、时间复杂度

    关于动态规划——背包问题的时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

    展开全文
  • 动态规划之背包问题——01背包

    千次阅读 2021-11-24 15:56:06
    文章目录一、01背包问题二、二维dp数组解决01背包问题1. 确定dp数组以及下标的含义2. 确定递推公式3. dp数组初始化4. 确定遍历顺序5. 举例推导dp数组三、一维dp数组解决01背包问题1. 确定dp数组以及下标的含义2. 一...


    背包问题中我们常见的就是 01背包完全背包。在leetcode的题库中主要就是这两种类型的题目。而完全背包又是也是01背包稍作变化而来,即:完全背包的物品数量是无限的。所以背包问题的基础就是01背包问题。完全背包问题请参考 动态规划之背包问题——完全背包

    在这里插入图片描述

    一、01背包问题

    有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

    每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是O(2^n)。

    所以需要动态规划来解题。

    二、二维dp数组解决01背包问题

    1. 确定dp数组以及下标的含义

    dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

    在这里插入图片描述

    2. 确定递推公式

    从两个方向推出来dp[i][j]

    1. 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以被背包内的价值依然和前面相同。)
    2. 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

    递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    3. dp数组初始化

    首先从dp[i][j]的定义出发,如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。

    状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。

    dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。

    j < weight[0]的时候,dp[0][j] 应该是 0,因为背包容量比编号0的物品重量还小。

    j >= weight[0]时,dp[0][j] 应该是value[0],因为背包容量放足够放编号0物品。

    for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步,如果把dp数组预先初始化为0了,这一步就可以省略。
        dp[0][j] = 0;
    }
    // 正序遍历
    for (int j = weight[0]; j <= bagWeight; j++) {
        dp[0][j] = value[0];
    }
    

    一开始把数组统一初始化为0,更方便。

    4. 确定遍历顺序

    有两个遍历维度:物品和背包重量。 所以要确定遍历顺序。

    两者都可以,先遍历物品好理解。

    先遍历物品,然后遍历背包重量:

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    
        }
    }
    

    先遍历背包,再遍历物品:

    // weight数组的大小 就是物品个数
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 1; i < weight.size(); i++) { // 遍历物品
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
    

    为什么两种顺序都可以?要理解递归的本质和递推的方向

    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。

    dp[i-1][j]dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向(包括正上方向),

    那么先遍历物品,再遍历背包的过程和先遍历背包,再遍历物品,dp[i][j]所需要的数据就是左上角,根本不影响dp[i][j]公式的推导。

    5. 举例推导dp数组

    在这里插入图片描述在这里插入图片描述最终结果就是dp[2][4]。

    完整Java测试代码:

    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
            //定义dp数组:dp[i][j]表示背包容量为j时,前i个物品能获得的最大价值
            int[][] dp = new int[wLen + 1][bagSize + 1];
            //初始化:背包容量为0时,能获得的价值都为0
            for (int j = weight[0]; j <= bagWeight; j++) {
                dp[0][j] = value[0];
            }
            //遍历顺序:先遍历物品,再遍历背包容量
            for (int i = 1; i <= weight.length; i++){
                for (int j = 1; j <= bagSize; j++){
                    if (j < weight[i - 1]){
                        dp[i][j] = dp[i - 1][j];
                    }else{
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                    }
                }
            }
        }
    

    三、一维dp数组解决01背包问题

    把二维dp降为一维dp,即使用一维滚动数组。

    在使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    滚动数组的由来,需要满足的条件是上一层可以重复利用,直接拷贝到当前层。

    dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。

    1. 确定dp数组以及下标的含义

    在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]

    2. 一维dp数组的递推公式

    dp[j]可以通过dp[j - weight[i]]推导出来,dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

    dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包加上物品i的价值。(也就是容量为j的背包,放入物品i了之后的价值即:dp[j]

    dp[j]有两个选择,一个是取自己dp[j] 相当于二维dp数组中的dp[i-1][j],即不放物品i,一个是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的。

    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    

    3. 一维dp数组如何初始化

    dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j],那么dp[0]就应该是0,因为背包容量为0所背的物品的最大价值就是0。

    假设物品价值都是大于0的,所以dp数组初始化的时候,都初始为0就可以了。

    4. 一维dp数组遍历顺序

    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    

    和二维dp的写法中,遍历背包的顺序是不一样的!

    一维dp遍历的时候,背包是从大到小:倒叙遍历是为了保证物品i只被放入一次!

    一旦正序遍历,那么物品0就会被重复加入多次。

    举一个例子:物品0的重量weight[0] = 1,价值value[0] = 15

    如果正序遍历

    dp[1] = dp[1 - weight[0]] + value[0] = 15

    dp[2] = dp[2 - weight[0]] + value[0] = 30

    此时dp[2]就已经是30了,意味着物品0,被放入了两次,所以不能正序遍历。

    倒叙就是先算dp[2]

    dp[2] = dp[2 - weight[0]] + value[0] = 15 (dp数组已经都初始化为0)

    dp[1] = dp[1 - weight[0]] + value[0] = 15

    所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。

    但对于二维dp,dp[i][j]都是通过上一层即dp[i - 1][j]计算而来,本层的dp[i][j]并不会被覆盖!

    两个嵌套for循环的顺序先遍历物品嵌套遍历背包容量

    因为一维dp的写法,背包容量一定是要倒序遍历,如果遍历背包容量放在上一层,那么每个dp[j]就只会放入一个物品,即:背包里只放入了一个物品。

    5. 举例推导dp数组

    一维dp,分别用物品0,物品1,物品2 来遍历背包,最终得到结果如下:
    在这里插入图片描述
    完整Java测试代码

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
            //定义dp数组:dp[j]表示背包容量为j时,能获得的最大价值
            int[] dp = new int[bagWeight + 1];
            //遍历顺序:先遍历物品,再遍历背包容量
            for (int i = 0; i < weight.length; i++){
                for (int j = bagWeight; j >= weight[i]; j--){
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }
    

    可以看出,一维dp 的01背包,要比二维简洁的多!而且空间复杂度还降了一个数量级!

    四、leetcode例题讲解01背包问题

    416. 分割等和子集

    leetcode题目链接:416. 分割等和子集

    给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

    示例一:

    输入:nums = [1,5,11,5]
    输出:true
    解释:数组可以分割成 [1, 5, 5][11]

    示例二:

    输入:nums = [1,2,3,5]
    输出:false
    解释:数组不能分割成两个元素和相等的子集。
    

    这道题目是要找是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

    那么只要找到集合里能够出现 sum / 2 的子集总和,就算是可以分割成两个相同元素和子集了。

    本题中我们要使用的是01背包,因为元素我们只能用一次

    首先,本题要求集合里能否出现总和为 sum / 2 的子集。那么来一一对应一下本题,看看背包问题如果来解决。

    1. 背包的体积为sum / 2
    2. 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
    3. 背包如何正好装满,说明找到了总和为 sum / 2 的子集。
    4. 背包中每一个元素是不可重复放入。

    1.确定dp数组以及下标的含义

    套到本题,dp[i]表示 背包总容量是i,最大可以凑成i的子集总和为dp[i]。

    2.确定递推公式

    本题,相当于背包里放入数值,那么物品i的重量是nums[i],其价值也是nums[i]。

    所以递推公式:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

    3.dp数组如何初始化

    题目中 只包含正整数的非空数组,所以非0下标的元素初始化为0就可以了。

    4.确定遍历顺序

    for(int i = 0; i < nums.size(); i++) {
        for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入,所以从大到小遍历
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    

    5.举例推导dp数组
    dp[i]的数值一定是小于等于i的。

    如果dp[i] == i 说明,集合中的子集总和正好可以凑成总和i,理解这一点很重要。

    用例1,输入[1,5,11,5] 为例,如图:
    在这里插入图片描述
    最后dp[11] == 11,说明可以将这个数组分割成两个子集,使得两个子集的元素和相等。

    完整Java代码:

    class Solution {
        public boolean canPartition(int[] nums) {
            if(nums == null || nums.length == 0) return false;
            int n = nums.length;
            int sum = 0;
            for(int num : nums){
                sum += num;
            }
            //总和为奇数,不能平分
            if(sum % 2 != 0) return false;
            int target = sum / 2;
            int[] dp = new int[target + 1];
            for(int i = 0; i < n; i++){
                for(int j = target; j >= nums[i]; j--){
                    //物品 i 的重量是 nums[i],其价值也是 nums[i]
                    dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
                }
            }
            return dp[target] == target;
        }
    }
    
    

    这道题目就是一道01背包应用类的题目,需要我们拆解题目,然后套入01背包的场景。

    01背包相对于本题,主要要理解,题目中物品是nums[i],重量是nums[i],价值也是nums[i],背包体积是sum/2。

    1049. 最后一块石头的重量 II

    leetcode题目链接:1049. 最后一块石头的重量 II

    有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

    每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

    如果 x == y,那么两块石头都会被完全粉碎;
    如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
    

    最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。

    示例一:

    输入:stones = [2,7,4,1,8,1]
    输出:1
    解释:
    组合 24,得到 2,所以数组转化为 [2,7,1,8,1],
    组合 78,得到 1,所以数组转化为 [2,1,1,1],
    组合 21,得到 1,所以数组转化为 [1,1,1],
    组合 11,得到 0,所以数组转化为 [1],这就是最优值。
    

    示例二:

    输入:stones = [31,26,33,21,40]
    输出:5
    

    本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这就回到了上一题分割等和子集,就化解成01背包问题了。

    背包体积为sum/2,物品的重量stones[i],物品的价值stones[i]。

    1.确定dp数组以及下标的含义

    dp[i] 表示容量为i的背包最多可以装dp[i]重的石头

    2.确定递推公式

    dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
    

    3.dp数组如何初始化

    同上。

    4.确定遍历顺序

    同上,先遍历物品,然后倒序遍历背包。

    完整Java代码:

    class Solution {
        public int lastStoneWeightII(int[] stones) {
            int sum = 0;
            for(int stone : stones){
                sum += stone;
            }
            int target = sum / 2;
            int[] dp = new int[target+1];
            for(int i = 0; i < stones.length; i++){
                for(int j = target; j >= stones[i]; j--){
                    dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);
                }
            }
            return sum - 2 * dp[target];
        }
    }
    

    494. 目标和

    leetcode题目链接:494. 目标和

    给你一个整数数组 nums 和一个整数 target 。

    向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 :

    例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。
    

    返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

    示例一:

    输入:nums = [1,1,1,1,1], target = 3
    输出:5
    解释:一共有 5 种方法让最终目标和为 3-1 + 1 + 1 + 1 + 1 = 3
    +1 - 1 + 1 + 1 + 1 = 3
    +1 + 1 - 1 + 1 + 1 = 3
    +1 + 1 + 1 - 1 + 1 = 3
    +1 + 1 + 1 + 1 - 1 = 3
    

    示例二:

    输入:nums = [1], target = 1
    输出:1
    

    本题其实是让数组中的数字分成添加正号的数字和与添加负号的数字和相等,就化解成01背包的组合问题。

    计算相等的方法有几种,就是组合问题。

    这里可以设添加负号的数字和为neg (也可以设正号的),总和为sum,则添加正号的数字和为sum - neg。

    要求 (sum - neg ) - neg= target,则neg = (sum - target) / 2。

    判断target的值和sum的值的大小,如果target大,没有方案,不能整除也没有方案,都是非负整数。

    转化为背包体积为neg= (sum - target) / 2,重量和价值都为nums[i]

    1.确定dp数组以及下标的含义

    dp[j] 表示元素和为j时的表达式数目

    2.确定递推公式

    dp[j] += dp[j], dp[j-nums[i]]
    

    求组合类问题的公式,都是类似这种。

    3.dp数组如何初始化

    从递归公式可以看出,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是在公式中一切递推结果的起源,如果dp[0]是0的话,递归结果将都是0。

    dp[0] = 1,理论上也很好解释,装满容量为0的背包,有1种方法,就是装0件物品。

    4.确定遍历顺序

    同上,先遍历物品,然后倒序遍历背包。

    完整Java代码:

    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            // 动态规划,一个正集,一个负集,和为target
            // 设元素和为sum,负号和为neg,正号和为sum-neg ,则(sum-neg)-neg = target, neg = (sum - target) / 2
            // 装满背包体积为neg,重量和价值为nums[i]的方法有几种
            // dp[j] 表示元素和为j时的表达式数目
            int sum = 0;
            for(int num : nums){
                sum += num;
            }
            int diff = sum - target; // 判断target的值和sum的值的大小,如果target大,没有方案,不能整除也没有方案,都是非负整数
            if(diff < 0 || diff % 2 != 0) return 0; 
            int neg = diff / 2; // 添加负号集的和
            int[] dp = new int[neg+1];
            dp[0] = 1;
            for(int i = 0; i < nums.length; i++){
                for(int j = neg; j >= nums[i]; j--){
                    dp[j] += dp[j - nums[i]];  // 组合问题
                }
            }
            return dp[neg];
        }
    }
    

    474. 一和零

    leetcode题目链接:474. 一和零

    给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

    请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。

    如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

    示例一:

    输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
    输出:4
    解释:最多有 5031 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
    其他满足题意但较小的子集包括 {"0001","1"}{"10","1","0"}{"111001"} 不满足题意,因为它含 41 ,大于 n 的值 3

    示例二:

    输入:strs = ["10", "0", "1"], m = 1, n = 1
    输出:2
    解释:最大的子集是 {"0", "1"} ,所以答案是 2

    这道题可以说是一个变形的01背包问题,本题中strs 数组里的元素就是物品,每个物品都是一个!

    而m 和 n相当于是一个背包,两个维度的背包。而不同长度的字符串就是不同大小的待装物品。

    1.确定dp数组以及下标的含义

    dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

    2.确定递推公式

    dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。

    dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

    然后我们在遍历的过程中,取dp[i][j]的最大值。

    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
    

    对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。

    这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。

    3.dp数组如何初始化

    因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。

    4.确定遍历顺序

    物品就是strs里的字符串,背包容量就是题目描述中的m和n。

    所以背包倒序遍历的时候需要遍历两个维度。

    完整Java代码:

    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            // 动态规划,01背包问题,背包有两个维度,一个m,一个n.
            // strs 数组里的元素就是物品,每个物品都是一个,不同长度的字符串都是待装物品
            // dp[i][j]表示最多有i个0,j个1的strs的最大子集长度
            // dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
            int zeroNum, oneNum;
            int[][] dp = new int[m+1][n+1];
            for(String str : strs){  // 先统计每个字符串0的个数和1的个数,遍历物品
                zeroNum = 0;
                oneNum = 0;
                for(char c : str.toCharArray()){
                    if(c == '0') zeroNum++;
                    else oneNum++;
                }
                for(int i = m; i >= zeroNum; i--){ // 遍历背包容量从后往前,两个背包
                    for(int j = n; j >= oneNum; j--){
                        dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                    }
                }
            }
            return dp[m][n];
        }
    }
    

    五、01背包问题总结

    1. 动规五步分析法

    1. 确定dp数组(dp table)以及下标的含义
    2. 确定递推公式
    3. dp数组如何初始化
    4. 确定遍历顺序
    5. 举例推导dp数组

    2. 背包递推公式

    问能否能装满背包(或者最多装多少):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ,对应题目如下:

    416. 分割等和子集

    1049. 最后一块石头的重量 II

    问装满背包有几种方法:dp[j] += dp[j - nums[i]] ,对应题目如下:

    494. 目标和

    问背包装满最大价值(多维背包问题):dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ,对应题目如下:

    474. 一和零

    3. 遍历顺序

    二维dp数组01背包先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历

    一维dp数组01背包只能先遍历物品再遍历背包容量,且第二层for循环是从大到小遍历

    动态规划其它题型总结:

    动态规划之背包问题——完全背包

    动态规划之打家劫舍系列问题

    动态规划之股票买卖系列问题

    动态规划之子序列问题

    参考:代码随想录:背包理论基础01背包

    展开全文
  • 背包问题总结 背包问题介绍 背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。...

    背包问题总结

    背包问题介绍

    背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkel和Hellman提出的。

    如下我分别总结了0-1背包问题,完全背包问题,以及背包的方案数问题

    1. 背包问题之0/1背包问题

    在这里插入图片描述

    题目描述

    有N件物品和一个容量为C的背包,其中第i件物品的重量为w[i],价值为v[i],求解哪些物品装入背包中可以使得背包中物品的价值最大?注意:每个物品只能选择一次

    问题分析:

    0-1背包问题的特点就在于每件物品只能选择一次,故只存在选或者不选两种情况,对于传入N件物品,容量为C的参数:

    我们定义w[N + 1],v[N + 1]: 存储物品的重量和价值
    注意:我们定义w[N+1],v[N+1]的目的在于使得数组下标和第i个物品相对应,相一致,同样也可以直接定义w[N],v[N],只是此时w[i],v[i]表示为第i+1个物品的重量和价值
    
    我们再定义dp[N + 1][C + 1]:其中dp[i][j]表示前i个物品可以选择的情况下,背包容量不超过j的最大价值
    此时我们存在两个选择:
    1)我们不选择第i个物品:dp[i][j] = dp[i - 1][j],即前i-1个物品,背包不超过j的最大价值
    2)我们选择第i个物品:dp[i][j] = dp[i - 1][j - w[i]] + v[i]
    即dp[i][j]为第i个物品的价值加上前i-1个物品,容量为j减去第i个物品的重量的最大价值之和
    但是注意:如果我们选择第i个物品,则必须保证当前背包容量j要大于第i个物品的重量,即j > w[i]
    

    在这里插入图片描述

    由此可得前i个物品,背包容量不超过j的情况下的最大价值为:
    i f   n o t   c h o o s e   w [ i ] : d p [ i ] [ j ] = d p [ i − 1 ] [ j ] if \space not \space choose \space w[i] : dp[i][j] = dp[i - 1][j] if not choose w[i]:dp[i][j]=dp[i1][j]

    i f   c h o o s e   w [ i ] : d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) if \space choose \space w[i]: dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i]) if choose w[i]:dp[i][j]=max(dp[i1][j],dp[i1][jw[i]]+v[i])

    最终,前N个物品,背包容量不超过C的最大价值为:
    d p [ N ] [ C ] dp[N][C] dp[N][C]

    代码实现:
    public class KnapsackProblems01 {
        /*
        * 01背包问题
        * N件物品和一个容量为V的背包:每件物品只能使用一次,第i件物品的体积是vi,价值为wi
        * 求解:将哪些物品装入背包,使得在不超过背包体积的情况下,总价值最大,输出最大价值
        * */
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            //n为输入的物品的个数
            int N = in.nextInt();
            //C为输入的背包的容量
            int C = in.nextInt();
            int[] w = new int[N + 1];//物品的重量
            int[] v = new int[N + 1];//物品的价值
            for (int i = 1; i <= N; i++) {
                w[i] = in.nextInt();
                v[i] = in.nextInt();
            }
    
            //定义二维的动态数组dp[][]
            //其中dp[i][j]:表示前i个物品,在不超过背包容量为j的情况下,得到的最大价值
            int[][] dp = new int[N + 1][C + 1];
            //给dp[0][j],dp[i][0]赋值初始值0:表示没有物品选择情况下,以及背包容量为0的情况下,最大价值均为0
            for (int i = 0; i <= N; i++) {
                dp[i][0] = 0;
            }
            for (int i = 0; i <= C; i++) {
                dp[0][i] = 0;
            }
            //进行dp[i][j]的赋值操作
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= C; j++) {
                    //不选择第i个物品的情况下,dp[i][j] = dp[i - 1][j]
                    dp[i][j] = dp[i - 1][j];
                    //如果第i个物品的重量v[i] <= j,则选择第i个物品,dp[i][j] = dp[i - 1][j - w[i]] + v[i]
                    //此时最大价值为dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - w[i]] + v[i]);
                    if (w[i] <= j) {
                        dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - w[i]] + v[i]);
                    }
                }
            }
            //此时dp[N][C]即为选择N个物品时,背包的最大价值
            int res = dp[N][C];
            System.out.println("该背包在" + N + "个物品中不重复的挑选,不超过背包总容量的情况下,最大价值为 :" + res);      
    }
    
    
    将二维dp优化为一维dp数组实现,实现动态规划的降维
    将二维dp数组降维到一维dp数组:
    由于dp[i][j]只和dp[i-1][j]的状态有关,故我们定义f[C+1],其中f[j]表示当前遍历的前j个物品可以选择,背包容量为j的情况下的最大价值
    将dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i]),将二维的i和i-1都去除掉,但是我们需要保证后面的是i - 1的状态:
    即dp[j] = max(dp[j],dp[j - w[i]] + v[i])
    故我们选择内循环从C --> w[i]进行循环:这样上面公式前面的dp[j]是前i个物品,背包为j的最大价值,后面的dp[j]和dp[j - w[i]]为前i - 1个物品,背包为j的最大价值
    
    //优化0-1背包问题代码:定义一维数组f[N+1]:其中f[j]表示前i个物品背包总容量为j的情况下的最大价值
            int[] f =  new int[C + 1];
            f[0] = 0;
            for (int i = 1; i <= N; i++) {
                for (int j = C; j >= w[i]; j--) {
                    //j从C到1:使得下面的f[j]是f[i - 1][j]和f[i - 1][j - w[i]] + v[i]的最大值
                    f[j] = Math.max(f[j],f[j - w[i]] + v[i]);
                }
            }
            //此时的f[C]是选择N个物品时,背包的最大价值
            int result = f[C];
            System.out.println("该背包在" + N + "个物品中不重复的挑选,不超过背包总容量的情况下,最大价值为 :" + result);
        }
    

    2. 背包问题之完全背包问题

    题目描述

    有N件物品和一个容量为C的背包,其中第i件物品的重量为w[i],价值为v[i],求解哪些物品装入背包中可以使得背包中物品的价值最大?注意:每个物品可以重复选择

    即题目的基础条件和前面的0-1背包问题相同,只是每件物品可以重复选择

    题目分析和代码实现

    我们仍然先选择使用二维的dp数组进行求解

    我们定义dp[N + 1][C + 1]:
    其中dp[i][j]表示前i个物品可以选择的情况下,背包容量不超过j的最大价值
    此时我们仍然存在两种选择:
    1)不选择第i个物品:dp[i][j] = dp[i - 1][j]
    2)选择第i个物品:此时由于存在可以重复选择的情况故我们可以重复进行选择,即此时可以选择1,2,3...k次(1< k <= j/w[i]),:
    for(int k = 1;k * w[i] <= j;k++) {
        dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - k * w[i]] + k * v[i]);
    }
    故我们联合上面两种选择情况,核心代码为:
    for(int i = 1;i <= N;i++) {
        for(int j = 1;j <= C;j++) {
            dp[i][j] = dp[i - 1][j];
            for(int k = 1;k * w[i] <= j;k++) {
                dp[i][j] = max(dp[i][j],dp[i - 1][j - k * w[i]] + k * v[i]);
            }
        }
    }
    最后的dp[N][C]即为前N个物品,背包容量为C的情况下的最大价值
    
    优化为一维dp数组
    同上面的0-1降维思想相同,由于前i种物品的状态只和前i-1种物品的状态有关,故我们可以选择进行降维,保证降维以后的一维数组dp[j],前者为前i个物品的最大价值,后者为前i-1个物品的最大价值
    代码实现:
    int[] dp = new int[C + 1];
    for(int i = 1;i <= N;i++) {
        for(int j = w[i];j <= C;j++) {
            dp[j] = max(dp[j],dp[j - w[i]] + v[i])
        }
    }
    最后的dp[C]即为前N个物品,背包容量为C的情况下的最大价值
    

    3. 背包问题之背包的方案数问题-----抛硬币问题(完全背包问题+背包方案数的结合问题讲解)

    问题描述

    给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007)

    在这里插入图片描述

    示例1:

     输入: n = 5
     输出:2
     解释: 有两种方式可以凑成总金额:
     5=5
     5=1+1+1+1+1
    

    示例2:

     输入: n = 10
     输出:4
     解释: 有四种方式可以凑成总金额:
     10=10
     10=5+5
     10=5+1+1+1+1+1
     10=1+1+1+1+1+1+1+1+1+1
    

    说明:

    注意:

    你可以假设:

    • 0 <= n (总金额) <= 1000000
    问题分析:
    该题的思路属于完全背包问题(每一种硬币可以重复选择)+背包的方案数问题(即有多少种表示法)
    我们同样需要进行动态规划思想进行求解,只是这里我们需要融合完全背包和方案数这两种思路
    假设有m个不同的硬币面值数可以选择,凑成的总金额为n,:
    定义数组w[m + 1]: w[i]表示第i种硬币的硬币面值数
    我们首先定义二维数组dp[m+1][n+1]:其中dp[i][j]表示前i种硬币面值可以选择的情况下,构成面值总金额为j的方案数
    1)当j = 0:即表示构成面值总金额为0的方案数,则只存在一种,即所有的面值硬币都不选择,故dp[i][0] = 1,i:0 ~ m
    2)当不选择第i个物品时,则dp[i][j] = dp[i - 1][j] = dp[i - 1][j - 0 * w[i]]
    3)当选择第i个物品时,则由于可以重复进行选择
    dp[i][j] = dp[i - 1][j - 1 * w[i]] + dp[i - 1][j - 2 * w[i]] + ...+ dp[i - 1][j - k * w[i]],其中k:1 ~ j/w[i]
    即dp[i][j]等于选择1个当前硬币面值,2个硬币面值...,k个硬币面值的方案数之和
    

    d p [ i ] [ [ j ] = ∑ l = 0 k d p [ i − 1 , j − l ∗ w [ i ] ] , k ∈ ( 1 , j / w [ i ] ) dp[i][[j] = \sum_{l=0}^k dp[i - 1,j - l *w[i]],k\in(1,j/w[i]) dp[i][[j]=l=0kdp[i1,jlw[i]],k(1,j/w[i])

    核心代码:
    static final int MOD = 1000000007;
    int [][] dp = new  int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            //不放入第i个物品
            dp[i][j] = dp[i- 1][j] % MOD;
            //放入第i个物品
            for (int k = 1; k * w[i] <= j; k++) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k * w[i]]) % MOD;
            }
        }
    }
    return dp[m][n];
    
    优化为一维dp数组:
    由于dp[i][j]只和dp[i - 1][j]的状态存在关联,故我们可以选择进行降维处理
    我们定义dp[n + 1]数组:其中dp[j]表示构成面值总金额为j的方案数
    则由于上面的动态转移方程,我们修改后的核心代码如下:
    static final int MOD = 1000000007;
    int[] dp = new int[n + 1];
    dp[0] = 1; //表示前i个物品构成面值为0的方案数为1
    for (int i = 1; i <= m; i++) {
        for (int j = w[i]; j <= n; j++) {
            dp[j] = (dp[j] + dp[j - w[i]]) % MOD;
        }
    }
    return dp[n];
    
    展开全文
  • 01背包问题: 01背包问题的特点:背包容量有限,物品只有一个,具有确定的体积和价值,我们的目标就是在不超过背包最大体积的情况下装入价值尽可能大的物品,让我们输出最大总价值 对于背包问题我们可以采用类似的...

    01背包问题:

    例题:传送门
    01背包问题的特点:背包容量有限,物品只有一个,具有确定的体积和价值,我们的目标就是在不超过背包最大体积的情况下装入价值尽可能大的物品,让我们输出最大总价值
    在这里插入图片描述

    对于背包问题我们可以采用类似的思考方式:

    以此为:

    1. 状态表示 考虑所有不同情况的结果存储方式
    2. 用集合表示背包问题的所有不同选法 f [ i ][ j ] 表示从0 ~ i 这些物品中选,最大背包容量为 j 的最大价值
    3. 然后考虑集合选法的条件, 数量 i 小于等于 物品总数 , 体积 j 小于等于 背包最大体积 V
    4. 至于背包问题的属性有已知几个情况:最大值,最小值, 数量
    5. 状态计算: 本质就是考虑如何根据上面的条件限制进行合理的集合划分 , 最终根据集合划分 进行状态转移方程的推导。

    01 背包问题实例:

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

    第 i 件物品的体积是 vi,价值是 wi。

    求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
    输出最大价值。

    输入格式
    第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

    接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

    输出格式
    输出一个整数,表示最大价值。

    数据范围
    0<N,V≤1000
    0<vi,wi≤1000
    输入样例

    4 5
    1 2
    2 4
    3 4
    4 5
    

    输出样例:

    8
    

    我们首先用二维数组的方式来表示背包集合的状态:
    对于f [ i ] [ j ] 的值我们可以从第 i 个物品选不选入手,如果第 i 个物品不选那么 f [ i ] [ j ] = f [ i -1 ] [ j ] 即等于上一层的最大价值 即从0~ i-1 个物品中选 且背包容量不超过 j 的最大值 , 如果在保证不超过背包容量 j 来选第 i 个物品 那么 f [ i ] [ j ] = f [ i -1 ] [ j - v [ i ] +w [ i ]这样我们就得到了容量不超过 j 而且海选则了 第 i 件物品的情况, f [ i ] [ j ] = max ( f [ i -1 ] [ j ], f [ i -1 ] [ j - v [ i ] + w[ i ])用循环依次进行这样的操作就得到了所有的状态下的最大价值,最后 f [ n ] [ V ] (n代表 n 个物品 数组的下标从0~ n ,V是背包最大容量) 就是最大价值。

    01 背包代码:

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    using namespace std;
    const int N=1010;
    int n,V;
    int v[N];
    int w[N];
    int dp[N][N];
    int maxn;
    int main(){
    	cin>>n>>V;
    	for(int i=1;i<=n;i++){
    		scanf("%d%d",&v[i],&w[i]);
    	}
    	for(int i=1;i<=n;i++){
    		for(int vj=1;vj<=V;vj++){
    		    if(vj<v[i]) dp[i][vj]=dp[i-1][vj];
    			else dp[i][vj]=max(dp[i-1][vj],dp[i-1][vj-v[i]]+w[i]);
    		}
    	}
    	cout<<dp[n][V]<<endl;
    	return 0;
    }
     
    

    时空复杂度分析和优化:

    时间复杂度为O ( n^2 )主要体现在得到所有状态的过程,这个目前没有更好的优化方式,空间复杂度为 O( n^2 ) 主要体现在我们用一个二维数组存储所有的状态的最大价值,但是通过观察代码我们可以发现每个 dp [ i ] [ j ] 只与 i -1 层的 dp [ i -1] [ j ] 和它之前的 dp [ i- v [ i ] ] [ j ] 有关所以我们没有必要对于i-1 层之前的数值进行存储 , 我们可以将空间缩小到一维数组, 但是要注意的是如果用一维数组(滚动数组方式)存储第二层的循环 将要逆序循环, 这是因为:如果正序循环,等到循环到 j 时 dp[ j ]用的是i层的数据,这是不符合我们的思路的,当逆序循环是用的就是i-1 层的了。
    下面是优化后的代码:

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    using namespace std;
    const int N=1010;
    int n,V;
    int v[N];
    int w[N];
    int dp[N];
    int maxn;
    int main(){
        cin>>n>>V;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&v[i],&w[i]);
        }
        for(int i=1;i<=n;i++){
            for(int j=V;j>=v[i];j--){ // 逆序循环 保证dp[j]用到的是上一层的数据
                   dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        cout<<dp[V]<<endl;
        return 0;
    }
     
    

    完全背包问题:

    例题:传送门
    01背包问题的升级版:每种物品有无限个了,而不是01背包问题中的一个,其他说明和01背包相同。

    我们依然用闫式dp分析法按照步骤求解,
    状态表示:集合 f[ i ][ j ] 表示从第1~i个物品中选 在背包容量不超过j的情况下物品的总最大价值
    属性:最大价值
    状态划分:可以将f[ i ][ j ]划分为好多种状态,即根据第i个物品选几个。
    f[ i ][ j ]=max(f[ i -1 ][ j ], f[ i -1][ j - v[i]]+w[i]…,f[i-1][j-s*v[i]+w[i]]…); 1
    f [ i ] [ j - v [ i ] ]= max(f[ i-1 ][ j ], f[ i - 1 ] [ j-v[i]] *w[i] …); 2
    在这里插入图片描述
    我们可以用2 式子加上w【i】从第一式的第二项开始替换
    从而得到一个比较普遍的式子,
    然后我们通过观察对比,这个式子和01背包问题的式子很像,所以可以用滚动数组来优化空间,
    在这里插入图片描述由于01 背包每一项用的是上一层(i-1) 的数值,但是完全背包问题由下标可得,是由本层中的前几项获得,所以
    状态转移公式为:

    //注意v要正序循环
    f[j]=max(f[j],f[j-v[i]]+w[i]);
    

    Code:

    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <cmath>
    #include <algorithm> 
    #include <map>
    #include <string.h>
    using namespace std;
    const int maxn=1010;
    int w[maxn],v[maxn];
    int n,m; 
    int f[maxn];
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		scanf("%d%d",&v[i],&w[i]);
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=v[i];j<=m;j++){
    			f[j]=max(f[j],f[j-v[i]]+w[i]);
    		}
    	}
    	cout<<f[m]<<endl;
    }
    

    时空复杂度分析:

    时间复杂度是O(n^2)空见复杂度为 O(n)n为10^4时都是可以接受的

    多重背包问题:

    例题:传送门
    多重背包问题就是每种物品由多个,不是无限也不是一个,我们可以把它转化为01 背包问题做,思路是:将多个物品拆分成一个一个的,当然这样一定有点麻烦,第二种想法是在数据量小的时候:加一层循环从0循环到s【i】(我们用s【i】来存储第i种物品的个数);
    然后套01背包的代码就可以了

    Code:

    
    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <cmath>
    #include <algorithm> 
    #include <map>
    #include <string.h>
    using namespace std;
    const int maxn=110;
    int w[maxn],v[maxn],s[maxn];
    int n,m; 
    int f[maxn];
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		scanf("%d%d%d",&v[i],&w[i],&s[i]);
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=m;j>=v[i];j--){
    			for(int k=0;k<=s[i] && k*v[i]<=j;k++){
    				f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
    			}
    		}
    	}
    	cout<<f[m]<<endl;
    }
    

    时空复杂度分析:

    时间复杂度O( n ^3) 空间复杂度O( n ) 时间复杂度确实不小,只能承受n不超过100的情况哦

    二进制优化降低时间复杂度:

    例题:传送门
    这道题的数据就加强了,N最坏情况为1000,V是2000,v,w,s都不超过2000,显然用上面的直接暴力做法一定超时,
    这里介绍一种二进制的优化方式,降低时间复杂度
    对于大数n从1到n进行枚举的这种情况优化明显。
    思路:
    对于每一个s[ i ] ,从1~ s[ i ] 可以用用几位二进制数进行表示,当表示的最大二进制数小于s[ i ] 时 最后可以用s[ i ]- 最大二进制数表示最后一项数字。
    这样我们就把一个大数分成了多组小的数字,用这写小的数字的组合可以组成1~ s[ i ]的任何一个数字。

    Code:

    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <cmath>
    #include <algorithm> 
    #include <map>
    #include <string.h>
    using namespace std;
    const int maxn=12010;
    int w[maxn],v[maxn],s;
    int n,V;
    int a,b;
    int f[maxn];
    int main(){
    	int cnt=1;
    	cin>>n>>V;
    	for(int i=1;i<=n;i++){
    		scanf("%d%d%d",&a,&b,&s);
    		int m=1;
    		while(m<=s){
    			s-=m;
    			v[cnt]=m*a,w[cnt++]=m*b;//分成用每次乘二表示的数打包成一件物品成一项加入数组
    			m*=2;
    		}
    		if(s>0){
    			v[cnt]=s*a,w[cnt++]=s*b;//剩下的单成以项,加入数组
    		}
    	}
    	for(int i=1;i<cnt;i++){
    		for(int j=V;j>=v[i];j--){
    				f[j]=max(f[j],f[j-v[i]]+w[i]);
    		}
    	}
    	cout<<f[V]<<endl;
    }
    

    时空复杂度分析:

    时间复杂度O( n^2logn) 在n小于1000时是可以接受的
    空间复杂度为O(n)

    分组背包问题:

    概念:分组背包问题就是,在每一物品组中只选择一个物品
    例题:传送门
    在这里插入图片描述

    Code:

    #include <cstdio>
    #include <iostream>
    #include <queue>
    #include <cstring>
    using namespace std;
    const int N=110;
    const int maxn=24010;
    int dp[N];
    int n,V; 
    int s[N],v[N][N],w[N][N];
    int main(){
    	cin>>n>>V;
    	for(int i=0;i<n;i++){
    		cin>>s[i];
    		for(int j=0;j<s[i];j++){
    			cin>>v[i][j]>>w[i][j];
    		}
    	}
    	for(int i=0;i<n;i++){
    		for(int j=V;j>=0;j--){
    			for(int k=0;k<s[i];k++){
    				if(j>=v[i][k]) dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
    			}
    		}
    	}
    	cout<<dp[V]<<endl;
    }
    
    
    展开全文
  • 0-1背包问题 有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci(即占用背包的空间容量),得到的价值是 Wi。 求解将哪些物品装入背包可使价值总和最大。 这是最基础的背包问题,特点是:每种物品...
  • 01背包问题 思路 每件物体只能使用一次,在固定容量的情况下,可以放入的最大价值。 当只使用前i件物品时,可以获得的最大价值一定是大于等于只使用前i-1件物品的。因此当不包含第i件物品时,f[i][j] = f[i-1][j]当...
  • 一、完全背包问题 1.1 题目 有 NNN 种物品和一个容量为 VVV 的背包,每种物品都有无限件可用。放入第 iii 种物品的费用是 CiC_iCi​,价值是 WiW_iWi​。求解:将哪些物品装入背包,可使这些物品的耗费的费用总和不...
  • 背包问题详解

    2021-08-20 10:28:04
    背包问题是一类经典的动态规划问题,它非常灵活,需要仔细琢磨体会,本文先对背包问题的几种常见类型作一个总结,再给出代码模板,然后再看看LeetCode上几个相关题目。 根据维基百科,背包问题(Knapsack problem...
  • 适用动态规划的问题必须满足最优化原理、无后效性和重叠性。  a.最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,...
  • 一、01背包问题: 有 N 件物品和一个容量为 V 的背包。第 i 件物品所占容量是 Ci,得到的价值是 Wi。求解将哪些物品装入背包可使价值总和最大。 根据第i件物品是否放入, dp[i,n] = max(dp[i-1,n],dp[i-1,n-Ci]),...
  • 背包问题总结分析背包问题是个很经典的动态规划问题,本博客对背包问题及其常见变种的解法和思路进行总结分析01背包问题介绍有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 v[i],...
  • 多重背包问题

    2020-12-31 03:54:17
    题目有N种物品和一个容量为V的背包。...基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值...
  • 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分01背包和无限背包,这里主要讨论01背包,即每个物品最多放一个。而无限背包可以转化为01背包。...
  • 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从子问题解得到原问题解。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用...
  • 《遗传算法的0-1背包问题(c语言)》由会员分享,可在线阅读,更多相关《遗传算法的0-1背包问题(c语言)(26页珍藏版)》请在人人文库网上搜索。1、基于遗传算法的0-1背包问题的求解摘要:一、前言组合优化问题的求解方法...
  • 01背包问题

    2021-05-20 08:51:32
    背包问题01背包问题完全背包问题多重背包问题暴力算法二进制优化分组背包 01背包问题 01背包问题 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 iii 件物品的体积是 viv_{i}vi​,价值是 wiw_{i}wi...
  • http://www.concretevitamin.com.cn/informatics/Pack/P02.html题目有N种物品和一个容量为V的背包,每种...基本思路这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相...
  • c语言背包问题 A O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有:0≤ f(n) ≤ cg(n) }; B O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有:0≤ cg(n) ≤ f(n) }; C O(g(n)) = { f(n) | 对于任何...
  • 背包问题是一类经典的动态规划问题,它非常灵活,需要仔细琢磨体会,本文先对背包问题的几种常见类型作一个总结,再给出代码模板,然后再看看LeetCode上几个相关题目。 根据维基百科,背包问题(Knapsack problem...
  • 毫无疑问,此时性价比最高的是物品4,我们把物品4放入背包当中,背包剩余的容量是8: 我们选择物品1放入背包背包剩余的容量是4: 于是,我们选择0.8份的物品5放入背包背包剩余的容量为0: 代码实现 public ...
  • 《回溯法解决01背包问题》由会员分享,可在线阅读,更多相关《回溯法解决01背包问题(21页珍藏版)》请在人人文库网上搜索。1、回溯法解决01背包问题,回溯法解决01背包问题,1、算法思想 2、问题描述 3、设计实现,回溯...
  • 背包问题讲解

    2021-02-12 08:04:30
    背包问题 前言:大年初一,祝大家新的一年心想事成~ 一、01背包 题目背景: 有 n 个物品,第 i 个物品体积为 vi ,价值为 ci ,现在有一个容积为 V 的背包,要求从这 n 件物品中选出一些装入背包中,使得装入...
  • 贪心算法解背包问题

    2021-02-12 20:17:29
    背包问题:与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1 <= i <= n。这2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,...
  • 并且可以尝试接触DP的一些重要的应用,最重要的要数背包问题背包问题是DP一个很大的分支(算是分支吧,我找不到其他更好的词来形容他了),同样也有非常多的变型,如最为基础的01背包,以及扩充出去的多重背包,完全...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 91,191
精华内容 36,476
关键字:

背包问题

友情链接: stowe_hydrology.zip