算法沉淀——动态规划之完全背包问题(leetcode真题剖析)

慈云数据 1年前 (2024-03-19) 技术支持 72 0

在这里插入图片描述

算法沉淀——动态规划之完全背包问题

  • 01.【模板】完全背包
  • 02.零钱兑换
  • 03.零钱兑换 II
  • 04.完全平方数

    完全背包问题是背包问题的一种变体,与01背包问题不同,它允许你对每种物品进行多次选择。具体来说,给定一个固定容量的背包,一组物品,每个物品有重量和价值,目标是找到在背包容量范围内,使得背包中的物品总价值最大的组合。

    相较于01背包问题,完全背包问题允许对每个物品进行多次选择,即每个物品都有无限件可用。

    动态规划解法:

    1. 定义状态: 通常使用二维数组dp[i][j]表示在前i个物品中,背包容量为j时的最大总价值。

    2. 状态转移方程: 考虑第i个物品,可以选择放入背包或者不放入。如果选择放入,那么总价值为dp[i][j-weight[i]] + value[i],即前i个物品的总价值加上当前物品的价值。如果选择不放入,那么总价值为dp[i-1][j],即前i-1个物品的总价值。因此,状态转移方程为:

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

      其中,dp[i-1][j]表示不放入第i个物品,dp[i][j-weight[i]] + value[i]表示放入第i个物品。

    3. 初始条件: 当i=0时,表示前0个物品,总价值为0;当j=0时,表示背包容量为0,总价值也为0。

    4. 遍历顺序: 外层循环遍历物品,内层循环遍历背包容量。

    5. 返回结果: 最终结果存储在dp[N][W]中,其中N为物品数量,W为背包容量。

    例子:

    假设有如下物品:

    物品1:重量=2,价值=3
    物品2:重量=3,价值=4
    物品3:重量=4,价值=5
    

    背包容量为W=8,我们要求解在这个条件下的最大总价值。

    按照上述动态规划解法,构建状态转移表如下:

    重量/价值      0   1   2   3   4   5   6   7   8
      ----------------------------------------------
      物品0        0   0   0   0   0   0   0   0   0
      物品1        0   0   3   6   9   12  15  18  21
      物品2        0   0   3   6   9   12  15  18  21
      物品3        0   0   3   6   9   12  15  18  21
    

    因此,最终结果为dp[3][8] = 21,表示在背包容量为8的情况下,最大总价值为21。这意味着最优解是选择物品1,物品2和物品3各两件放入背包。

    01.【模板】完全背包

    题目链接:https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

    描述

    你有一个背包,最多能容纳的体积是V。

    现在有n种物品,每种物品有任意多个,第i种物品的体积为vi,价值为wi。

    (1)求这个背包至多能装多大价值的物品?

    (2)若背包恰好装满,求至多能装多大价值的物品?

    输入描述:

    第一行两个整数n和V,表示物品个数和背包体积。

    接下来n行,每行两个vi和wi表示第i种物品的体积和价值。

    1≤n,V≤1000

    输出描述:

    输出有两行,第一行输出第一问的答案,第二行输出第二问的答案,如果无解请输出0。

    示例1

    输入:

    2 6
    5 10
    3 1
    

    输出:

    10
    2
    

    示例2

    输入:

    3 8
    3 10
    9 1
    10 1
    

    输出:

    20
    0
    

    说明:

    无法恰好装满背包。
    

    示例3

    输入:

    6 13
    13 189
    17 360
    19 870
    14 184
    6 298
    16 242
    

    输出:

    596
    189
    

    说明:

    可以装5号物品2个,达到最大价值298*2=596,若要求恰好装满,只能装1个1号物品,价值为189.
    

    思路

    第一问:

    1. 状态表示:
      • dp[i][j] 表示从前 i 个物品中挑选,总体积不超过 j,所有选法中能挑选出的最大价值。
      • 状态转移方程:
        • 根据最后一步的状况,分情况讨论
          • 选 0 个第 i 个物品:相当于去前 i - 1 个物品中挑选,总体积不超过 j,最大价值为 dp[i - 1][j]。
          • 选 1 个第 i 个物品:相当于去前 i - 1 个物品中挑选,总体积不超过 j - v[i]。此时最大价值为 dp[i - 1][j - v[i]] + w[i]。
          • 综上,状态转移方程为:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])。
          • 初始化:
            • 多加一行,将第一行初始化为 0,因为什么也不选时,满足体积不小于 j 的情况,此时价值为 0。
            • 填表顺序:
              • 从上往下填表。
              • 返回值:
                • 根据状态表示,返回 dp[n][V]。

    第二问:

    1. 状态表示:
      • dp[i][j] 表示从前 i 个物品中挑选,总体积正好等于 j,所有选法中能挑选出来的最大价值。
      • 状态转移方程:
        • dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])。
        • 在使用 dp[i][j - v[i]] 时,需要判断 j >= v[i] 且 dp[i][j - v[i]] 表示的状态是否存在,即 dp[i][j - v[i]] != -1。
        • 初始化:
          • 多加一行,将第一个格子设置为 0,因为正好能凑齐体积为 0 的背包;但是第一行后面的格子都设置为 -1,因为没有物品,无法满足体积大于 0 的情况。
          • 填表顺序:
            • 从上往下填表。
            • 返回值:
              • 由于最后可能凑不成体积为 V 的情况,因此返回之前需要特判一下。

    空间优化:

    对于背包问题,一般都可以使用「滚动数组」来进行空间上的优化,即减少状态表示的维度。

    在 01 背包问题中,优化的结果为:

    1. 删掉所有的横坐标。
    2. 修改一下 j 的遍历顺序。

    这样的优化是因为在计算 dp[i][j] 时,只依赖于上一行 dp[i-1][j] 和 dp[i-1][j-v[i]],而 dp[i-1][j-v[i]] 在当前行的计算过程中已经被更新过,因此不需要保留整个二维数组。

    代码

    #include 
    #include 
    #include 
    using namespace std;
    const int N=1002;
    int n,V,v[N],w[N];
    int dp[N][N];
    int main() {
        cin>>n>>V;
        for(int i=1;i>v[i]>>w[i];
        for(int i=1;i
                dp[i][j]=dp[i-1][j];
                if(j=v[i]) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
            }
        cout
                dp[i][j]=dp[i-1][j];
                if(j=v[i]&&dp[i][j-v[i]]!=-1) 
                    dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
            }
        cout
        const int INF=0x3f3f3f3f;
    public:
        int coinChange(vector
            int n=coins.size();
            vector
                    dp[i][j]=dp[i-1][j];
                    if(j=coins[i-1]) dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1);
                }
            return dp[n][amount]=INF?-1:dp[n][amount];
        }
    };
    
    public:
        int change(int amount, vector
            int n=coins.size();
            vector
                    dp[i][j]=dp[i-1][j];
                    if(j=coins[i-1]) dp[i][j]=dp[i][j]+dp[i][j-coins[i-1]];
                }
            return dp[n][amount];
        }
    };
    
        const int INF=0x3f3f3f3f;
    public:
        int numSquares(int n) {
            int m=(int)sqrt(n);
            vector
                    dp[i][j]=dp[i-1][j];
                    if(j=i*i) dp[i][j]=min(dp[i][j],dp[i][j-i*i]+1);
                }
            return dp[m][n];
        }
    };
    
微信扫一扫加客服

微信扫一扫加客服