动态规划＜八＞ 完全背包问题及其余背包问题
目录
例题引入---找到解决问题模版
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];}