[Algorithm][动态规划][二维费用的背包问题][一和零][盈利计划]详细讲解

目录

0.原理讲解

  • 本质仍然是背包问题，但是相较于普通的背包问题，只是限制条件多了一个而已

1.一和零

1.题目链接

2.算法原理详解

  • 思路：

    • 确定状态表示 -> dp[i][j]的含义

      • dp[i][j][k]：从前i个字符串中挑选，字符0的个数不超过j，字符1的个数不超过k，所有的选法中，最大的长度

    • 推导状态转移方程：根据最后一个位置的情况，分情况讨论
      请添加图片描述

    • 初始化：

      • 三个维度都多开一“行”虚拟结点
      • j, k这两个维度的初始化都可以交给DP阶段

    • 确定填表顺序：i从小到大

    • 确定返回值：dp[len][n][m]

  • 滚动数组优化空间
    • 大致思路与完全背包一致
    • 操作
      • 删除所有的i
      • 修改一下j, k的遍历顺序
    • 注意：不要去强行解释优化后的妆台表示以及状态转移方程，费时费力还没啥意义

3.代码实现

// v1.0
int findMaxForm(vector<string>& strs, int n, int m) 
{
    int len = strs.size();
    vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));

    for(int i = 1; i <= len; i++)
    {
        // 先统计字符串中0 1的个数
        int a = 0, b = 0;
        for(auto& ch : strs[i - 1])
        {
            ch == '0' ? a++ : b++;
        }

        // DP
        for(int j = 0; j <= n; j++)
        {
            for(int k = 0; k <= m; k++)
            {
                dp[i][j][k] = dp[i - 1][j][k];
                if(j >= a && k >= b)
                {
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
                }
            }
        }
    }

    return dp[len][n][m];
}
---------------------------------------------------------------------------------
// v2.0 滚动数组优化
int findMaxForm(vector<string>& strs, int n, int m) 
{
    int len = strs.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    for(int i = 1; i <= len; i++)
    {
        // 先统计字符串中0 1的个数
        int a = 0, b = 0;
        for(auto& ch : strs[i - 1])
        {
            ch == '0' ? a++ : b++;
        }

        // DP
        for(int j = n; j >= a; j--)
        {
            for(int k = m; k >= b; k--)
            {
                dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);
            }
        }
    }

    return dp[n][m];
}

2.盈利计划

1.题目链接

2.算法原理详解

  • 思路：

    • 确定状态表示 -> dp[i][j]的含义

      • dp[i][j][k]：从前i个计划中挑选，总人数不超过j，总利润至少为k，一共有多少种选法

    • 推导状态转移方程：根据最后一个位置的情况，分情况讨论
      请添加图片描述

    • 初始化：

      • 三个维度都多开一“行”虚拟结点
      • dp[0][j][0] = 1
      • k这个维度的初始化可以交给DP阶段

    • 确定填表顺序：i从小到大

    • 确定返回值：dp[len][n][m]

  • 滚动数组优化空间
    • 大致思路与完全背包一致
    • 操作
      • 删除所有的i
      • 修改一下j, k的遍历顺序
    • 注意：不要去强行解释优化后的妆台表示以及状态转移方程，费时费力还没啥意义

3.代码实现

// v1.0
int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) 
{
    const int MOD = 1e9 + 7;
    int len = g.size();

    // Init
    vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));
    for(int j = 0; j <= n; j++)
    {
        dp[0][j][0] = 1;
    }

    // DP
    for(int i = 1; i <= len; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            for(int k = 0; k <= m; k++)
            {
                dp[i][j][k] = dp[i - 1][j][k];
                if(j >= g[i - 1])
                {
                    dp[i][j][k] += dp[i - 1][j - g[i - 1]][max(0, k - p[i - 1])];
                }
                dp[i][j][k] %= MOD;
            }
        }
    }

    return dp[len][n][m];
}
------------------------------------------------------------------------------
// v2.0 滚动数组优化
int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) 
{
    const int MOD = 1e9 + 7;
    int len = g.size();

    // Init
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for(int j = 0; j <= n; j++)
    {
        dp[j][0] = 1;
    }

    // DP
    for(int i = 1; i <= len; i++)
    {
        for(int j = n; j >= g[i - 1]; j--)
        {
            for(int k = m; k >= 0; k--)
            {
                dp[j][k] += dp[j - g[i - 1]][max(0, k - p[i - 1])];
                dp[j][k] %= MOD;
            }
        }
    }

    return dp[n][m];
}