DP：完全背包+多重背包问题

2024-06-21 12:12
文章标签 背包 dp 多重 完全 问题

本文主要是介绍DP：完全背包+多重背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

完全背包和01背包的区别就是：可以多次选

一、完全背包（模版）

【模板】完全背包_牛客题霸_牛客网

#include <iostream>
#include<string.h>
using namespace std;
const int N=1001;
int n,V,w[N],v[N],dp[N][N];
//dp[i][j]表示从前i个物品选，体积不超过j的最大价值
//dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i],dp[i-1][j-2v[i]]+2w[i]……)
//数学dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]]+w[i]……)
//dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]])
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=1;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;//解决第二问 //dp[i][j]表示从前i个物品选，体积正好为j的最大价值memset(dp,0,sizeof dp);//约定-1表示状态选不到 当i=0时 j>=1时  必然是没有状态的for(int j=1;j<=V;++j) dp[0][j]=-1;for(int i=1;i<=n;++i)for(int j=1;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])<<endl;return 0;
}

滚动数组的优化策略：

 区分：01背包的优化得是从右往左，而完全背包的优化得是从左往右

#include <iostream>
#include<string.h>
using namespace std;
const int N=1001;
int n,V,w[N],v[N],dp[N];
//dp[i][j]表示从前i个物品选，体积不超过j的最大价值
//dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i],dp[i-1][j-2v[i]]+2w[i]……)
//数学dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]]+w[i]……)
//dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]])
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;//解决第二问 //dp[i][j]表示从前i个物品选，体积正好为j的最大价值memset(dp,0,sizeof dp);//约定-1表示状态选不到 当i=0时 j>=1时  必然是没有状态的for(int j=1;j<=V;++j) dp[j]=-0x3f3f3f3f;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]<0?0:dp[V])<<endl;return 0;
}

 二、零钱兑换

. - 力扣（LeetCode）

class Solution {
public:int coinChange(vector<int>& coins, int amount) {//dp[i][j]表示从前i个里面选 正好凑成j所需要的最少硬币个数//如果不选i dp[i-1][j]//选1个i   dp[i-1][j-coins[i-1]]+1//dp[i][j]=min(dp[i-1][j],dp[i-1][j-coins[i-1]]+1,dp[i-1][j-2coins[i-1]]+2……)//dp[i][j-coins[i-1]]=min(dp[i-1][j-coins[i-1]],dp[i-1][j-2coins[i-1]]+1……)//dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1)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=1;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];}
};

 滚动数组优化：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {//dp[i][j]表示从前i个里面选 正好凑成j所需要的最少硬币个数//如果不选i dp[i-1][j]//选1个i   dp[i-1][j-coins[i-1]]+1//dp[i][j]=min(dp[i-1][j],dp[i-1][j-coins[i-1]]+1,dp[i-1][j-2coins[i-1]]+2……)//dp[i][j-coins[i-1]]=min(dp[i-1][j-coins[i-1]],dp[i-1][j-2coins[i-1]]+1……)//dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1)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];}
};

三、零钱兑换II

. - 力扣（LeetCode）

class Solution {
public:int change(int amount, vector<int>& coins) {//dp[i][j]表示从前i个硬币选，正好可以凑成总金额的硬币组合数//如果i不选 dp[i][j]+=dp[i-1][j]//如果i选1个 dp[i][j]+=dp[i-1][j-coins[i-1]]//dp[i][j]+=dp[i-1][j-coins[i-1]]+=dp[i-1][j-2coins[i-1]]……//dp[i][j]+=dp[i][j-coins[i-1]]int n=coins.size();//分析初始化 当j=0 都是一种选法  当i=0时 无论如何凑不出j 状态无效vector<vector<int>> dp(n+1,vector<int>(amount+1));dp[0][0]=1;for(int i=1;i<=n;++i)for(int j=0;j<=amount;++j) //不会越界，可以从0开始{dp[i][j]+=dp[i-1][j];if(j>=coins[i-1]) dp[i][j]+=dp[i][j-coins[i-1]];}return dp[n][amount];}
};

滚动数组做优化：

class Solution {
public:int change(int amount, vector<int>& coins) {//dp[i][j]表示从前i个硬币选，正好可以凑成总金额的硬币组合数//如果i不选 dp[i][j]+=dp[i-1][j]//如果i选1个 dp[i][j]+=dp[i-1][j-coins[i-1]]//dp[i][j]+=dp[i-1][j-coins[i-1]]+=dp[i-1][j-2coins[i-1]]……//dp[i][j]+=dp[i][j-coins[i-1]]int n=coins.size();//分析初始化 当j=0 都是一种选法  当i=0时 无论如何凑不出j 状态无效vector<int> dp(amount+1);dp[0]=1;for(int i=1;i<=n;++i)for(int j=coins[i-1];j<=amount;++j) //不会越界，可以从0开始dp[j]+=dp[j-coins[i-1]]; //+= 0不会影响填表return dp[amount];}
};

四、完全平方数

. - 力扣（LeetCode）

class Solution {
public:
//不能用贪心策略 比如说1 4 9   组成12    444比9111好int numSquares(int n) {//1 4 9 16 25……//dp[i][j]表示从前i个数选，刚好为j的最少数量const int INF=0x3f3f3f3f;int m=sqrt(n);vector<int> dp(n+1,INF);//i=0的时候 不可能凑成j  j=0时 i取1dp[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是平方数 所以必然能凑出来}
};

五、数位成本和为目标值的最大数字（经典dp还原）

. - 力扣（LeetCode）

class Solution {
public:string largestNumber(vector<int>& nums, int t) {//考虑数值长度问题，每个数字有相应成本，且长度均为1 //有若干物品，求给定费用下所能选择的最大价值  （完全背包）//得到的就是最大位数 然后从后往前想办法还原回来vector<int> dp(t+1,-0x3f3f3f3f);//会有不存在的状态//dp[i][j]表示前i个数选择 正好为j的最大选择数目dp[0]=1;for(int i=1;i<=9;++i)for(int j=nums[i-1];j<=t;++j)dp[j]=max(dp[j],dp[j-nums[i-1]]+1);//此时 dp[t]里存的就是选择的最大位数 然后要想办法进行还原if(dp[t]<0) return "0";string ret;//开始还原 从后往前还原for(int i=9;i>=1;--i){int u=nums[i-1];while(t>=u&&dp[t]==dp[t-u]+1)//说明选到这个数了{ret+=to_string(i);t-=u;}}return ret;}
};

六、获得分数的方法数（多重背包）

. - 力扣（LeetCode）

 该种类型题的具体分析请看第7题！！

class Solution {
public:const int MOD=1e9+7;int waysToReachTarget(int target, vector<vector<int>>& types) {//dp[i][j]表示从前i个数选 恰好分数为j的方案数 选择方式是types[1] //如果不选这个数 dp[i-1][j]//如果选 1个  dp[i-1][j-p[0]] //如果选2个  dp[i-1][j-2p[0]]int n=types.size();vector<vector<int>> dp(n+1,vector<int>(target+1));//初始化当i为0时 dp[0][0]=1;for(int i=1;i<=n;++i){int count=types[i-1][0],mark=types[i-1][1]; //count表示这道题的题数（选择次数）  mark表示这道题的分数for(int j=0;j<=target;++j){dp[i][j]=dp[i-1][j];for(int k=1;k<=count;++k){if(j>=k*mark) dp[i][j]=(dp[i][j]+dp[i-1][j-k*mark])%MOD;}}}return dp[n][target];}
};

滚动数组优化 

class Solution {
public:const int MOD=1e9+7;int waysToReachTarget(int target, vector<vector<int>>& types) {//dp[i][j]表示从前i个数选 恰好分数为j的方案数 选择方式是types[1] //如果不选这个数 dp[i-1][j]//如果选 1个  dp[i-1][j-p[0]] //如果选2个  dp[i-1][j-2p[0]]vector<int> dp(target+1);//初始化当i为0时 dp[0]=1;for(auto&p:types){int count=p[0],mark=p[1]; //count表示这道题的题数（选择次数）  mark表示这道题的分数       //会用到上一层的状态，所以滚动数组应该要从后往前for(int j=target;j>=0;--j){count=min(count,j/mark);for(int k=1;k<=count;++k)dp[j]=(dp[j]+dp[j-k*mark])%MOD;}}return dp[target];}
};

进阶优化：

class Solution {
public:const int MOD=1e9+7;int waysToReachTarget(int target, vector<vector<int>>& types) {//dp[i][j]表示从前i个数选 恰好分数为j的方案数 选择方式是types[1] //如果不选这个数 dp[i-1][j]//如果选 1个  dp[i-1][j-p[0]] //如果选2个  dp[i-1][j-2p[0]]//dp[i][j]+=dp[i-1][j-p[0]]……//dp[i][j-p[0]+=dp[i-1]][j-]vector<int> dp(target+1);//初始化当i为0时 dp[0]=1;for(auto&p:types){int count=p[0],mark=p[1]; //count表示这道题的题数（选择次数）  mark表示这道题的分数       //会用到上一层的状态，所以滚动数组应该要从后往前for(int j=mark;j<=target;++j)dp[j]=(dp[j]+dp[j-mark])%MOD;for(int j=target;j>=(count+1)*mark;--j)dp[j] = (dp[j] - dp[j - mark*(count + 1)] + MOD) % MOD; // 两个同余前缀和的差//防止搞出负数}return dp[target];}
};

七、带和限制的子多重集合的数目（经典多重背包模版题）

. - 力扣（LeetCode）

 直接做滚动数组优化：

class Solution {
public:const int MOD=1e9+7;int countSubMultisets(vector<int>& nums, int l, int r) {//01背包 每个数选或者不选 限制范围是l-r//dp[i][j]表示从前i个数选  凑成和恰好为j//但是需要一个哈希表来帮助我们知道每个数究竟可以选多少次unordered_map<int,int> hash;int total=0;for(auto&e:nums) {total+=e;++hash[e];}if(l>total) return 0;r=min(r,total);vector<int> dp(r+1);//初始化 i=0时 无数可选dp[0]=hash[0]+1;hash.erase(0);int t=0;for(auto[x,c]:hash) //x是数 c是他的限制次数for(int j=r;j>=x;--j){c=min(c,j/x);for(int k=1;k<=c;++k)    //费时间 想办法用新的状态dp[j]=(dp[j]+dp[j-k*x])%MOD; }int sum=0;for(int j=l;j<=r;++j)sum=(sum+dp[j])%MOD;return sum;}
};

我们会发现由于数据量太大，用循环会超时，因此我们在这里不能用k那一层循环！！得换个方式

class Solution {
public:const int MOD=1e9+7;int countSubMultisets(vector<int>& nums, int l, int r) {//01背包 每个数选或者不选 限制范围是l-r//dp[i][j]表示从前i个数选  凑成和恰好为j//但是需要一个哈希表来帮助我们知道每个数究竟可以选多少次//类比完全背包的状态 dp[]unordered_map<int,int> hash;int total=0;for(auto&e:nums) {total+=e;++hash[e];}if(l>total) return 0;r=min(r,total);vector<int> dp(r+1);dp[0]=hash[0]+1;hash.erase(0);// dp[i][j]+=  dp[i-1][j-x]+dp[i-1][j-2*x]……// dp[i][j-x]+=dp[i-1][j-2x]+dp[i-1][j-3x]……int sum=0;for(auto[x,c]:hash){sum = min(sum+x*c,r);//目前为止 能选的元素和之多为sum for (int j = x; j <= sum; j++)dp[j] = (dp[j] + dp[j - x]) % MOD; // 原地计算同余前缀和for (int j =sum;j >= x * (c + 1); j--)dp[j] = (dp[j] - dp[j - x * (c + 1)] + MOD) % MOD; // 两个同余前缀和的差//防止搞出负数}int ret=0;for(int j=l;j<=r;++j)ret=(ret+dp[j])%MOD;return ret;}
};

 

这篇关于DP：完全背包+多重背包问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1081186。

相关文章

linux生产者，消费者问题

linux生产者，消费者问题

pthread_cond_wait() ：用于阻塞当前线程，等待别的线程使用pthread_cond_signal()或pthread_cond_broadcast来唤醒它。 pthread_cond_wait() 必须与pthread_mutex 配套使用。pthread_cond_wait()函数一进入wait状态就会自动release mutex。当其他线程通过pthread
阅读更多...
问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示
阅读更多...
2024.6.24 IDEA中文乱码问题（服务器 控制台 TOMcat）实测已解决

2024.6.24 IDEA中文乱码问题（服务器 控制台 TOMcat）实测已解决

1.问题产生原因： 1.文件编码不一致：如果文件的编码方式与IDEA设置的编码方式不一致，就会产生乱码。确保文件和IDEA使用相同的编码，通常是UTF-8。2.IDEA设置问题：检查IDEA的全局编码设置和项目编码设置是否正确。3.终端或控制台编码问题：如果你在终端或控制台看到乱码，可能是终端的编码设置问题。确保终端使用的是支持你的文件的编码方式。 2.解决方案： 1.File -> S
阅读更多...
vcpkg安装opencv中的特殊问题记录（无法找到opencv_corexd.dll）

vcpkg安装opencv中的特殊问题记录（无法找到opencv_corexd.dll）

我是按照网上的vcpkg安装opencv方法进行的（比如这篇：从0开始在visual studio上安装opencv（超详细，针对小白）），但是中间出现了一些别人没有遇到的问题，虽然原因没有找到，但是本人给出一些暂时的解决办法： 问题1： 我在安装库命令行使用的是 .\vcpkg.exe install opencv 我的电脑是x64，vcpkg在这条命令后默认下载的也是opencv2:x6
阅读更多...
问题-windows-VPN不正确关闭导致网页打不开

问题-windows-VPN不正确关闭导致网页打不开

为什么会发生这类事情呢？ 主要原因是关机之前vpn没有关掉导致的。 至于为什么没关掉vpn会导致网页打不开，我猜测是因为vpn建立的链接没被更改。 正确关掉vpn的时候，会把ip链接断掉，如果你不正确关掉，ip链接没有断掉，此时你vpn又是没启动的，没有域名解析，所以就打不开网站。 你可以在打不开网页的时候，把vpn打开，你会发现网络又可以登录了。 方法一 注意：方法一虽然方便，但是可能会有
阅读更多...
vue同页面多路由懒加载-及可能存在问题的解决方式

vue同页面多路由懒加载-及可能存在问题的解决方式

先上图，再解释 图一是多路由页面，图二是路由文件。从图一可以看出每个router-view对应的name都不一样。从图二可以看出层路由对应的组件加载方式要跟图一中的name相对应，并且图二的路由层在跟图一对应的页面中要加上components层，多一个s结尾，里面的的方法名就是图一路由的name值，里面还可以照样用懒加载的方式。 页面上其他的路由在路由文件中也跟图二是一样的写法。 附送可能存在
阅读更多...
vue+elementui--$message提示框被dialog遮罩层挡住问题解决

vue+elementui--$message提示框被dialog遮罩层挡住问题解决

最近碰到一个先执行this.$message提示内容，然后接着弹出dialog带遮罩层弹框。那么问题来了，message提示框会默认被dialog遮罩层挡住，现在就是要解决这个问题。 由于都是弹框，问题肯定是出在z-index比重问题。由于用$message方式是写在js中而不是写在html中所以不是很好直接去改样式。 不过好在message组件中提供了customClass 属性，我们可以利用
阅读更多...
Visual Studio中，MSBUild版本问题

Visual Studio中，MSBUild版本问题

假如项目规定了MSBUild版本，那么在安装完Visual Studio后，假如带的MSBUild版本与项目要求的版本不符合要求，那么可以把需要的MSBUild添加到系统中，然后即可使用。步骤如下：            假如项目需要使用V12的MSBUild，而安装的Visual Studio带的MSBUild版本为V14。 ①到MSDN下载V12 MSBUild包，把V12包解压到目录（
阅读更多...
YOLO v3 训练速度慢的问题

YOLO v3 训练速度慢的问题

一天一夜出了两个模型，仅仅迭代了200次   原因：编译之前没有将Makefile 文件里的GPU设置为1，编译的是CPU版本，必须训练慢   解决方案： make clean  vim Makefile make   再次训练 速度快了，5分钟迭代了500次
阅读更多...
Pycharm配置conda环境(解决新版本无法识别可执行文件问题)

Pycharm配置conda环境(解决新版本无法识别可执行文件问题)

引言: 很多小伙伴在下载最新版本的pycharm或者更新到最新版本后为项目配置conda环境的时候，发现文件夹目录中无法显示可执行文件(一般为python.exe)，以下就是本人遇到该问题后试验和解决该问题的一些方法和思路。 一般遇到该问题的人群有两种，一种是刚入门对pycharm进行conda环境配置的小白(例如我)，不熟悉相关环境配置的操作和过程，还有一种是入坑pycharm有段时间的老手
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2