动态规划＜八＞ 完全背包问题及其余背包问题

目录

例题引入---找到解决问题模版

LeetCode 经典OJ题

1.第一题

 2.第二题

 3.第三题

 其余的一些背包问题

1.二维费用的背包问题

例题引入---找到解决问题模版

OJ 传送门 牛客 DP42 【模板】完全背包

画图分析:

 使用动态规划解决(第二问与第一问的不同之处用绿色来标记)

1.状态表示

dp[i][j]表示从前i个物品中挑选，总体积不超过j的所有选法中，所挑选出来的最大价值

dp[i][j]表示从前i个物品中挑选，总体积等于j的所有选法中，所挑选出来的最大价值

2.状态转移方程

3.初始化  根据01背包问题得知，我们只需初始化第一行即可

4.填表顺序   从上往下填每一行，每一行从左往右

5.返回值  对于第一问的是直接返回dp[n][V]

第二问则是需要判断下dp[n][V]==-1?0:dp[n][V] 

具体代码   ---优化前

#include <iostream>
#include <string.h>
using namespace std;
const int N=1010;
int n,V;
int w[N],v[N],dp[N][N];
int main()
{
    //读入数据
    cin>>n>>V;
    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]) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
      }
    cout<<dp[n][V]<<endl;

    //解决第二问
    memset(dp,0,sizeof dp);
    for(int j=1;j<=V;++j) dp[0][j]=-1;
    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] && dp[i][j-v[i]]!=-1) 
        dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
      }
    cout<<(dp[n][V]==-1? 0:dp[n][V]);
    return 0;
}

做优化

优化后的代码

#include <iostream>
#include <string.h>
using namespace std;
const int N=1010;
int n,V;
int w[N],v[N],dp[N];
int main()
{
    //读入数据
    cin>>n>>V;
    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<=V;++j)
      {
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
      }
    cout<<dp[V]<<endl;

    //解决第二问
    memset(dp,0,sizeof dp);
    for(int j=1;j<=V;++j) dp[j]=-1;
    for(int i=1;i<=n;++i)
      for(int j=v[i];j<=V;++j)
      {
        if(dp[j-v[i]]!=-1) 
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
      }
    cout<<(dp[V]==-1? 0:dp[V]);
    return 0;
}

LeetCode 经典OJ题

1.第一题

OJ 传送门 LeetCode<322> 零钱兑换

画图分析：

 使用动态规划解决

1.状态表示

dp[i][j]表示从前i个硬币中挑选，总和正好等于j，所有的选法中，最少的硬币数

2.状态转移方程

3.初始化

4.填表顺序  从上往下每一行，每一行从左往右

5.返回值   dp[n][amount]>=INF? -1:dp[][amount]

具体代码

 int coinChange(vector<int>& coins, int amount) 
    {
        const const int INF=0x3f3f3f3f;
        int n=coins.size();

        vector<vector<int>> dp(n+1,vector<int>(amount+1));
        for(int j=1;j<=amount;++j) dp[0][j]=INF;
        for(int i=1;i<=n;++i)
         for(int j=0;j<=amount;++j)
         {
            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];
    }


//优化后
 int coinChange(vector<int>& coins, int amount) 
    {
        const const int INF=0x3f3f3f3f;
        int n=coins.size();

        vector<int>dp(amount+1,INF);
        dp[0]=0;
        for(int i=1;i<=n;++i)
         for(int j=coins[i-1];j<=amount;++j)
            dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
        
        return dp[amount]>=INF? -1:dp[amount];
    }

 2.第二题

OJ 传送门 LeetCode<518> 零钱兑换II

画图分析：

 使用动态规划解决

1.状态表示

dp[i][j]表示从前i个硬币中挑选，总和正好等于j，一共有多少种选法

2.状态转移方程

3.初始化 初始化第一行，第一个位置前0个凑出0元，即什么都不选，是一种方法，初始化为1，其余位置是凑不出来的，即初始化为0

4.填表顺序   从上往下每一行，每一行从左往右

5.返回值   dp[n][amount]

具体代码 

int change(int amount, vector<int>& coins) 
    {
        vector<unsigned int> dp(amount + 1); 
        dp[0] = 1; 
        for(int i=1;i<=coins.size();++i) 
         for(int j = coins[i-1]; j <= amount; j++) 
           dp[j] += dp[j - coins[i-1]];
        return dp[amount];
    }

 3.第三题

OJ 传送门 LeetCode<279> 完全平方数

 画图分析：

对于本题可以从左往右进行挑选完全平方数，来合成数n,且每个完全平方数都能重复进行选择

这就是完全背包问题 使用动态规划解决

1.状态表示

dp[i][j]表示从前i个完全平方数中进行挑选，总和恰好为j,完全平方数的数量

2.状态转移方程

3.初始化  初始化第一行，第一个位置初始化为0，其余位置的状态是不存在的，因为题目求的是min,为不影响填表，初始化为一个较大值ox3f3f3f3f

4.填表顺序  从上往下，从左往右

5.返回值 dp[sqrt(n)][n]

具体代码：

int numSquares(int n) 
    {
        int m=sqrt(n);
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int j=1;j<=n;++j) dp[0][j]=0x3f3f3f3f;
        for(int i=1;i<=m;++i)
            for(int j=0;j<=n;++j)
            {
                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];
    }

//优化后
 int numSquares(int n) 
    {
        int m=sqrt(n);
        vector<int>dp(n+1,0x3f3f3f3f);
        dp[0]=0;
        for(int i=1;i<=m;++i)
            for(int j=i*i;j<=n;++j)
            {
                dp[j]=min(dp[j],dp[j-i*i]+1);
            }
        return dp[n];
    }

 其余的一些背包问题

1.二维费用的背包问题

二位费用的背包问题简单来说就是指有两个限定条件的背包问题

OJ 传送门 LeetCode<474>一和零

画图分析

 本题目简单来说，就是从数组中挑选字符串，挑出来的字符串要共同满足1和0 的最多出现次数的条件，因此是一个背包问题，且要满足两个条件，因此是二维费用的背包问题

使用动态规划解决

1.状态表示

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

2.状态转移方程

3.初始化  对于三维的也一样，仅需初始化关于i=0的这些数据，根据状态表示，都初始化为1

4.填表顺序    i从小到大

5.返回值       dp[len][m][n]

具体代码

int findMaxForm(vector<string>& strs, int m, int n) 
    {
        int len=strs.size();
        vector<vector<vector<int>>>dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1)));
        for(int i=1;i<=len;++i)
        {
            //统计字符串中0 1的个数
            int a=0,b=0;
            for(auto ch:strs[i-1])
            {
                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]=max(dp[i][j][k],dp[i-1][j-a][k-b]+1);
                }
            }
        }
        return dp[len][m][n];
    }

//优化
int findMaxForm(vector<string>& strs, int m, int n) 
    {
        int len=strs.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        for(int i=1;i<=len;++i)
        {
            //统计字符串中0 1的个数
            int a=0,b=0;
            for(auto ch:strs[i-1])
            {
                if(ch=='0') ++a;
                else ++b;
            }
            for(int j=m;j>=a;--j)//从大到小
            {
                for(int k=n;k>=b;--k)
                {
                    dp[j][k]=max(dp[j][k],dp[j-a][k-b]+1);
                }
            }
        }
        return dp[m][n];
    }