小游戏网站建设公司,xampp安装wordpress,营销软文200字,销售管理软件哪个好用文章目录 概要说明分组背包模板例题1思路code模板例题2思路code 有依赖的背包问题模板例题思路code 背包问题求方案数模板例题思路code 背包问题求具体方案模板例题思路code 概要说明
本文讲分组背包、有依赖的背包、 背包问题求方案数以及背包问题求具体方案 入门篇(01背包和… 文章目录 概要说明分组背包模板例题1思路code模板例题2思路code 有依赖的背包问题模板例题思路code 背包问题求方案数模板例题思路code 背包问题求具体方案模板例题思路code 概要说明
本文讲分组背包、有依赖的背包、 背包问题求方案数以及背包问题求具体方案 入门篇(01背包和完全背包问题)传送门 进阶篇(多重、混合、二维费用背包)传送门
分组背包
模板例题1
acwing-分组背包问题
思路
分组背包也是01背包的一个变形01背包中我们有n个物品在这题中我们有n个组别每个组别有k个物品 因此我们可以对每个组别都进行01背包在当前组别选出最优解的情况下在进行下一轮组别的01背包 它的状态转移方程和01背包一样在01背包的基础上改动一点点即可 它的时间复杂度在 O ( n 3 ) O(n^3) O(n3)
code
const int N1e35;
int cnt[N],f[N],w[N][N],v[N][N];
void solve(){int W,n,t1;cin n W;for(int i1;in;i){cin cnt[i];for(int j1;jcnt[i];j){cin w[i][j] v[i][j];} }for(int i1;in;i) for(int jW;j0;--j)for(int k1;kcnt[i];k){if(jw[i][k]){f[j]max(f[j],f[j-w[i][k]]v[i][k]);}}cout f[W];return ;
}模板例题2
通天之分组背包
思路
这题在模板例题1的基础上稍微变动了一点点它没有给你确切的组数 因此我们需要先找出最大的组数并另开一个数组存当前组数的下标 剩下的和模板例题1差不多代码如下
code
const int N1e35;
int cnt[N],f[N],w[N],v[N],g[N][N];//g数组中行存的是组别列存的是个数它的取值存的是下标
void solve(){int W,n,t0;cin W n;for(int i1;in;i){int x;cin w[i] v[i] x;cnt[x];tmax(t,x);g[x][cnt[x]]i;}for(int i1;it;i) for(int jW;j0;--j)for(int k1;kcnt[i];k){int stg[i][k];//取出当前组别的下标if(jw[st]){f[j]max(f[j],f[j-w[st]]v[st]);}}cout f[W];return ;
}有依赖的背包问题
模板例题
有依赖的背包问题
思路
首先我们明确一点想要取出子节点必须取出父节点 那么想要价值尽可能大我们必须倒着遍历这颗树 遍历树最基本的算法是什么呢 很显然我们很快就能想到dfs回溯的思想先来看这张图
先看左边这条线1-2-4我们将这颗树的节点分开来看4的父节点为22的父节点1 那么我们想取出4的价值首先必须取出2的价值我们想取出2的价值首先必须取出1的价值
我们倒着遍历树当我们遍历到4时发现4没有子节点这时我们就回溯到前一个状态2 在回溯之前我们将4的价值存入到一个数组中这时我们考虑状态2它有2种选择选或者不选 这时候它的状态转移方程和01背包是一样的 注意在选状态4物品之前需要减去状态2的重量因为状态2必须先选才能选状态4
接着我们将选完的状态回溯到前一个状态1同理我们在选物品之前需要先减去状态1的重量 然后它也是有2种选择选或者不选
对于其他线路也是同理最终都会回溯到状态1那么我们只需要从状态1开始进行dfs遍历到树的叶节点时开始回溯即可
讲完思路接着讲一下如何用代码实现出来 首先我们需要标记根节点的位置用vector建树将子节点存入父节点中 开一个二维数组行代表节点列代表重量w所存的值为价值v 将根节点进行dfs将当前 f [ x ] [ w − W ] 都标记为 v x 代表节点 w 代表重量 W 为背包容量 v 为价值 f[x][w-W]都标记为vx代表节点w代表重量W为背包容量v为价值 f[x][w−W]都标记为vx代表节点w代表重量W为背包容量v为价值 这样方便我们递归回溯时进行状态转移 接着我们一直遍历当前节点的子节点将子节点进行dfs循环直到不能遍历为止 这样我们就像上面所说的遍历到4不能遍历回溯到2的状态 接着进行01背包的状态转移方程当前循环结束在回溯到上一次的状态 最终dfs循环结束输出 f [ r o o t ] [ W ] f[root][W] f[root][W]
接下来我们看代码
code
const int N1e35;
int w[N],v[N],f[N][N];
vectorint g[N];
int n,W;
void dfs(int x){for(int iw[x];iW;i) f[x][i]v[x];//将w~W的重量都标记为vfor(auto y : g[x]){dfs(y);//一直循环子节点直到不能循环为止for(int jW;jw[x];--j)for(int k0;kj-w[x];k){//所选的物品必须减去当前重量f[x][j]max(f[x][j],f[x][j-k]f[y][k]);//选子节点的物品还是不选子节点的物品}}
}
void solve(){cin n W;int root;for(int i1;in;i){int x;cin w[i] v[i] x;if(x-1) rooti;//标记else g[x].push_back(i);//建树}dfs(root);cout f[root][W];return ;
}背包问题求方案数
模板例题
背包问题求方案数
思路
这种类型的题目不需要我们求具体的价值但是需要我们求最优价值的方案总数 那么我们首先还是需要算出最大的价值然后将能到达当前价值的方案数进行相加
那么具体该如何实现呢 我们需要在01背包的基础上多开一个g数组用于统计方案数 对于每步的状态来源我们都有两种情况一种是本身一种是当前容量减去物品容量加上物品价值 这时我们新开一个变量temp这个变量统计两种情况的最大值 若temp等于本身那么 g [ i ] g[i] g[i]加上它本身 若temp等于当前容量减去物品容量加上物品价值那么 g [ i ] g [ j − w [ i ] g[i]g[j-w[i] g[i]g[j−w[i] 每次加上都记得要取模 然后将当前状态 f [ j ] f[j] f[j]更新为temp 最后找出背包所能容量的最大价值遍历f数组若当前 f [ i ] f[i] f[i]等于最大价值加上 g [ i ] g[i] g[i]
接下来看代码进一步理解
code
const int N1e35;
int f[N],g[N],w[N],v[N];
void solve(){int n,W;cin n W;for(int i1;in;i){cin w[i] v[i];}g[0]1;//若不选物品方案数为1for(int i1;in;i)for(int jW;jw[i];--j){int tempmax(f[j],f[j-w[i]]v[i]);//temp为当前状态的最大值int c0;//统计数量if(tempf[j]) c(cg[j])%mod;//加上方案数if(tempf[j-w[i]]v[i]) c(cg[j-w[i]])%mod;f[j]temp,g[j]c;//状态转移}int maxn0;for(int i0;iW;i) maxnmax(maxn,f[i]);//找到最大价值int ans0;for(int i0;iW;i){if(f[i]maxn) ans(ansg[i])%mod;//统计个数}cout ans;return ;
}背包问题求具体方案
模板例题
背包问题求具体方案
思路
首先我们需要回溯到原来的状态这时候我们开一维数组就会丢失原来的状态这时候必须开二维数组来存储数据 我们先考虑一个问题我们是从前往后回溯还是从后往前回溯呢 答案很明显我们需要从前往后回溯 为什么呢 题目要求输出字典序最小的方案
我们拿一个例子来说明 3 3 1 2 2 4 2 4
物品总数为3背包容量为3每个物品先输入重量在输入价值 如果我们从后往前回溯那么我们求出的具体方案为1 3(最后将数组颠倒一下) 可是答案很明显为1 2这样字典序才是最小的 那么我们就将这种方法pass掉
那么我们一开始需要第n件物品的状态转移到第1件物品这样 f [ 1 ] [ W ] f[1][W] f[1][W]就为最大的价值 首先还是先套01背包的模板只不过从1开始变为从n开始 然后我们从序号1遍历到序号n判断当前的状态是不是由当前价值加上上一个状态转移过来的即 f [ i ] [ j ] f [ i 1 ] [ j − w [ i ] ] v [ i ] f[i][j]f[i1][j-w[i]]v[i] f[i][j]f[i1][j−w[i]]v[i] 若满足则当前背包容量减去 w [ i ] w[i] w[i],直接输出当前下标即可
接下来看代码
code
const int N1e35;
int f[N][N],v[N],w[N],cnt[N];
void solve(){int n,W;cin n W;for(int i1;in;i){cin w[i] v[i];}for(int in;i1;--i)//倒着来for(int j0;jW;j){f[i][j]f[i1][j];if(jw[i]) f[i][j]max(f[i][j],f[i1][j-w[i]]v[i]);}for(int i1,jW;in;i){if(jw[i] f[i][j]f[i1][j-w[i]]v[i]){//判断状态cout i ;j-w[i];}}return ;
}
