【动态规划】须知少时凌云志，曾许人间第一流 - 二维01背包问题

用户11369350

发布于 2025-02-25 14:34:00

4300

代码可运行

文章被收录于专栏：Java,后端开发,网站开发,数据结构,算法分析.Java,后端开发,网站开发,数据结构,算法分析.

运行总次数：0

代码可运行

本篇博客给大家带来的是二维01背包问题之动态规划解法技巧.

🐎文章专栏: 动态规划

🚀若有问题评论区见

❤ 欢迎大家点赞评论收藏分享

如果你不知道分享给谁,那就分享给薯条.

你们的支持是我不断创作的动力 .

1. 一和零

题目链接: 474. 一和零

题目内容:

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

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

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

示例 1：

输入：strs = “10”, “0001”, “111001”, “1”, “0”, m = 5, n = 3

输出：4

解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。

其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = “10”, “0”, “1”, m = 1, n = 1

输出：2

解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

第一步分析

在前面学习01背包问题和完全背包问题的时候, 我们遇到的限制条件只有一个, 这道题中出现了两个:

最多有 m 个 0 和 n 个 1

只有一个限定条件的01背包问题的状态表示是这样定义的: dpi表示从前 i 个物品中选, 总体积不超过 j ,所有选法的最大价值.

类比过来本题的状态表示可以这么定义:

dpik表示从前 i 个字符串中挑选, 字符0个数不超过 j , 字符1 的个数不超过 k,所有选法中的最大长度.

第二步动态规划

状态表示 dpik表示从前 i 个字符串中挑选, 字符0个数不超过 j , 字符1 的个数不超过 k,所有选法中的最大长度.
状态转移方程

以某 i 位置是否选择来划分情况:

如果选了strsi的话, j需要减去strsi含有的0个数,k需要减去strsj含有的1个数. 这里假设strsi有a个0,b个1;

不选strsi: dpik = dpi-1k;①

选了strsi: dpik = dpi-1k-b;②

结合①②又题目所求的是最大子集长度,所以:

dpik = Math.max(dpi-1k,dpi-1k-b+1);

②式应用的前提是: j >= a && k >= b

初始化

多创建了一行一列一竖,处理两个细节:

dp表与原数组下标之间的对应关系: 因为状态转移方程中并没有涉及到原数组strs的式子,所以可以不用管这一步.
初始化虚拟节点: 因为有j >= a && k >= b的限制(在一维的题中有解释过,具体可以看我之前的文章),所以只需初始化i = 0的节点即可, i=0 的时候没有字符串课选,最大长度为0,所以dp0k = 0;
填表顺序看状态转移方程, 要想填dpik 就得直到dpi-1k 和 dpi-1k-b, 所以需要保证 i 按小到大的顺序去填写.
返回值根据状态表示并结合题目要求,返回dpstrs.length()n即可.
代码优化跟01背包问题的优化方式一毛一样, 删掉第一维i,然后两层for循环的填表顺序改为从大到小. 详细看01背包问题, 文章链接: 01背包问题

第三步代码实现

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //优化前:
        // int len = strs.length;
        // int[][][] dp = new int[len+1][m+1][n+1];
        // for(int i = 1;i <= len;++i) {
        //     //统计各个字符串的个数
        //     int a = 0;//记录0的个数
        //     int b = 0;//记录1的个数
        //     for(char ch : strs[i-1].toCharArray()) {
        //         if(ch == '0') {
        //             a++;
        //         }else {
        //             b++;
        //         }
        //     }
        //     for(int j = 0;j <= m;++j) {
        //         for(int k = 0;k <= n;++k) {
        //             dp[i][j][k] = dp[i-1][j][k];
        //             if(j >= a && k >= b) {
        //                 dp[i][j][k] = Math.max(dp[i][j][k],dp[i-1][j-a][k-b]+1);
        //             }
        //         }
        //     }
        // }
        // return dp[len][m][n];

        //优化后:
        int len = strs.length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 1;i <= len;++i) {
            //统计各个字符串的个数
            int a = 0;//记录0的个数
            int b = 0;//记录1的个数
            for(char ch : strs[i-1].toCharArray()) {
                if(ch == '0') {
                    a++;
                }else {
                    b++;
                }
            }
            for(int j = m;j >= a;--j) {
                for(int k = n;k >= b;--k) {
                    dp[j][k] = Math.max(dp[j][k],dp[j-a][k-b]+1);
                }
            }
        }
        return dp[m][n];
    }
}

2. 盈利计划

题目链接: 879. 盈利计划

题目内容:

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profiti 的利润，它要求 groupi 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为盈利计划。并且工作的成员总数最多为 n 。

有多少种计划可以选择？因为答案很大，所以返回结果模 10^9 + 7 的值。

示例 1：

输入：n = 5, minProfit = 3, group = 2,2, profit = 2,3

输出：2

解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。

总的来说，有两种计划。

示例 2：

输入：n = 10, minProfit = 5, group = 2,3,5, profit = 6,7,8

输出：7

解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。

有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

第一步动态规划

状态表示 dpik表示在前 i 个工作中选,参与成员总数不超过 j,产生的利润至少为k,总共有多少种选法.
状态转移方程

根据 i 位置的选择与否来划分情况:

profiti不选, dpik = dpi-1k;①

profiti选, dpik = dpi-1 j-groupi][k-profiti].Ⅱ

考虑到profiti 有可能大于 k,而数组的下标不能为负数. 所以Ⅱ式不能这么写.那要怎么办呢?

如果profiti > k, 但是profiti利润就满足了条件那么前i-1个位置的利润可以为0.

所以, dpik = dpi-1 j-groupi][Math.max(0,(k-profiti))];②

根据①②并结合题目要求

dpik = dpi-1k + dpi-1j-groupi][Math.max(0,(k-profiti))];

使用②式的前提是: j >= groupi && k <= profiti;

初始化

多创建了一行一列一竖,处理两个细节:

dp表与原数组下标之间的对应关系: i – i-1;
初始化虚拟节点. j 和 k都是有限制的,j = 0和k = 0在填表中填即可, 主要初始化 i=0时的情况. 当i=0 && k =0时, 无论 j 是多少dp00 = 1; 即当没有工作的时候,利润至少为0,人数不超过 j.有几种选法, 只有一种,就是不选.
填表顺序与上一道题一样, i从小到大填写.
返回值根据状态表示并结合题目要求: return dpprofit.lengthminprofit;
优化
删除第一维i
两层for循环的填表顺序改为从大到小

第二步代码实现

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        //优化前:
        // int m = profit.length;
        // int[][][] dp = new int[m+1][n+1][minProfit+1];
        // //2. 初始化
        // for(int i = 0;i <= n;i++) {
        //     dp[0][i][0] = 1;
        // }
        // for(int i = 1;i <= m;++i) {
        //     for(int j = 0;j <= n;++j) {
        //         for(int k = 0;k <= minProfit;++k) {
        //             dp[i][j][k] += dp[i-1][j][k];
        //             if(j >= group[i-1]) {
        //                 dp[i][j][k] += dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])];
        //                 dp[i][j][k] %=  1e9+7;
        //             }
        //         }
        //     }
        // }
        // return dp[m][n][minProfit];

        //优化后:
        int m = profit.length;
        int[][] dp = new int[n+1][minProfit+1];
        //2. 初始化
        for(int i = 0;i <= n;i++) {
            dp[i][0] = 1;
        }
        for(int i = 1;i <= m;++i) {
            for(int j = n;j >= group[i-1];--j) { // 从右往左遍历
                for(int k = minProfit;k >= 0;--k) {
                        dp[j][k] += dp[j-group[i-1]][Math.max(0,k-profit[i-1])];
                        dp[j][k] %=  1e9+7;
                }
            }
        }
        return dp[n][minProfit];
    }
}