背包p2014 1997 ctsc
01背包问题
## 01背包问题 ### 一.问题描述 #### 背包问题的基本条件 现有(n + 1)种物品，每种物品只有一个，编号由0到n，每种物品有两个属性，质量weight，价值value；有一个背包，容量(最大承受质量)为capacity； 为了描述每一种物品，我们使用w[n + 1]和v[n + 1] ......
2023牛客暑期多校练营6 A-Tree 树上背包+并查集
## 2023牛客暑期多校练营6 A-Tree 树上背包+并查集 ### [题目链接](https://codeforces.com/problemset/problem/1385/F) ### 题意： 给出一棵树，节点为黑色或者白色，定义整棵树的贡献为，任意白点到任意黑点所经过路径上的最大边权之和 ......
有依赖的背包问题
# [10. 有依赖的背包问题 - AcWing题库](https://www.acwing.com/problem/content/description/10/) 考虑树形 `DP`。 假设我们对于 $u$，已经计算完毕子节点 $v$，那么我们应该如何合并方案呢？ 有一种方式是指数级枚举子节点的 ......
多重背包
# [6. 多重背包问题 III - AcWing题库](https://www.acwing.com/problem/content/6/)  先讲bitset用法： 1，基础 下标：$5~4~3~2~1~0$ 数字：$0~0~0~0~1~0$ $bitset$ $s$表示一个$n$位的二进制数，空间复杂度： ......
【LuoGu 5322】[BJOI2019] 排兵布阵 ——分组背包
# [BJOI2019] 排兵布阵 ## 题目描述 小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。 如果一名玩家向第 $i$ 座城 ......
P1757 通天之分组背包
自 01背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 01 背包， 他的物品大致可分为 k 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。 ###1. 动态规划 分组背包 ``` int maxval(int v,vector&c,vector&w, ......
树上背包优化 - 时间复杂度证明
# 树上背包优化 - 时间复杂度证明 - 树上背包顾名思义，就是在树上做背包 dp - 树上背包的模板代码如下 ```cpp void dfs(int x){ sz[x] = 1; if(x >= n - m + 1){ dp[x][1] = -a[x]; return; } for(PII e : ......
背包DP笔记
## 背包问题 ### 01 背包问题 有 $n$ 件物品和一个容量为 $V$ 的背包，第 $i$ 件物品的体积为 $w[i]$，价值为 $v[i]$。请选择将哪些物品装入背包，使得价值总和最大。 思路：每种物品仅有一件，可以选择放或不放。令 $f[i][j]$ 表示前 $i$ 件物品放入一个容量为 ......
c++算法之动态规划：01背包
什么是动态规划？ 动态规划算法（dynamic programing），是一种由递推为基础的比贪心更稳定的一种优化策略，为运筹学的一部分。就是通过以递推为基础的手段非暴力求出最值。 它的总体思想其实就是一个比较过程：假如你有一个数据，它的价值是x，代价为y，如果用动态规划就是和你不加这个元素和你加上 ......
贪心算法--背包问题--分数背包
> 博客地址：https://www.cnblogs.com/zylyehuo/ *  * 
# 背包问题 (to be continued) ## 0x01 01 背包 ### Problem 有 $N$ 件物品和一个容量为 $V$ 的背包. 第 $i$ 件物品的费用是 $v_i$ , 价值是 $w_i$ . 求 $\max \left\{ \left. \sum_{1\leq i\leq ......
整数划分问题（完全背包）（总方案数和最小方案数）
完全背包解决整数划分问题： 总方案数： 完全背包:在前i个数中选，且总和恰好等于j的方案数f[i][j] = f[i - 1][j] + f[i - 1][j - v] 化成一维： f[j] += f[j - v]; 这种求总方案数的情况需要把f初始化为0，然后f[0]初始化为1，最后累加f[j] ......
[动态规划第一节]背包问题汇总
- ### 背包问题 - 动态规划思路： - #### 状态表示 f(i, j) - 状态由几维表示 - 表示的**集合**是什么 - 所有选法 - 选法条件 - 只考虑前i个物品 - 总体积 > n >> m; for(int i = 1; i > v[i] >> w[i]; //f[1~n][0 ......
背包问题变式总结
# 01背包 ## 01背包完全装满求方案数 > [Acwing 278 数字组合](https://www.acwing.com/problem/content/280/) 状态表示：二维 集合：所有从前 $i$ 个数里面选，且和是 $j$ 的选法的集合 属性：选法的数量 状态计算 分为 选 $i ......
背包问题基础模型全解
# 背包问题 ## 01背包 > [Acwing 2. 01背包问题](https://www.acwing.com/problem/content/description/2/) 状态表示：二维 集合：只从前 $i$ 个物品里面选择总体积 $\leq j$ 选法的集合 属性：选法价值的最大值 状态 ......
背包
### 01背包 给定 $n$ 件物品，每个物品有重量 $w_{i}$ 和价值 $c_{i}$，一个物品只有一件，求容量不超过 $m$ 的背包最多可以装多少价值物品 定义 $f_{i,j}$ 表示前 $i$ 件物品在容量不超过 $j$ 的背包下可以获得的最大价值则有 $f_{i,j}=\max\{f ......
浅谈背包
## 引入 背包问题，是大多数 oier 在学习动态规划（下文用 dp 代替）的过程中，最先接触到的问题。它看似简单，有蕴含着无穷的变化。本文便对作者接触过的背包问题做一个总结。 背包问题，一般情况下指：你有 $n$ 个物品和一个容量为 $m$ 的背包，每个物品有重量 $w$ 和价值 $v$，各个物 ......
背包问题的一些模板
## 01背包问题： 无优化 for(int i=1;i<=n;i++) { for(int c=0;c<=m;c++) { f[i][c]=f[i-1][c]; if(c>=w[i]) f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]); } } 一维数组优化： fo ......
零一背包与完全背包
零一背包 给定一组物品，每个物品有自己的重量和价值，以及一个背包的容量。目标是选择一些物品放入背包中，使得在不超过背包容量的情况下，背包中物品的总价值最大化。 思路 1、定义问题dp[i][j]:表示前i个物品中当容量为j时的最大价值 2、定义状态转移方程 (1) Dp[i][j] = math.m ......
多重背包 (单调队列)
[题目链接](https://www.acwing.com/problem/content/6/ "题目链接") *** ``` #include using ll = long long; const int N = 1E3 + 5 , M = 2E4 + 5; int n,m; int v[N] ......
【树上背包】洛谷P2014 [CTSC1997] 选课
# 【树上背包】洛谷P2014 [CTSC1997] 选课 题目链接：[P2014 [CTSC1997\] 选课 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P2014) ## 题目描述 在大学里每个学生，为了 ......
总结： [01背包] 空间优化后内层循环为啥是逆序的?
总结： [01背包] 空间优化后内层循环为啥是逆序的?首先，这是一个困扰了不少人的问题，虽然网上有挺多的解释，但是有的想起来比较费劲，于是乎，就有了这篇题解 题目分析 首先，01背包问题是一个非常非常非常经典的动态规划问题(后文简称“动规”或“dp”)。 因为百度百科上的题目分析比较详细 （我比较懒 ......
[刷题笔记] Luogu P2014 [CTSC1997] 选课
[Problem](https://www.luogu.com.cn/problem/P2014) ### Solution 我们发现本题中有好多主从关系，即要想取用一个儿子必须先取用她的父亲。构成了一个森林，处理不便。 有个小技巧，就是将0号节点参与建树，最后所求节点数就变成了$m+1$，且把森林 ......
[算法学习笔记] [算法总结] dp背包模型
### 前言 dp背包模型属dp的一种，可以帮助我们快速的转移状态，解题。dp背包模型题的关键是判断这是哪种背包，属于什么类型的dp，只有判断出这是什么类型的背包，才能进一步朝这个方向思考。 ### 01背包 01背包的常规形式是有$n$种物品，每间物品都有重量和价值两个参数。每件物品都可以选or不 ......
[算法学习笔记] 多重背包--二进制拆分
### 多重背包 回顾一下多重背包是什么？有$n$种物品，每个物品都有有限个，每个物品都有重量和价值两个参数，你有一个限重为$W$的背包，求背包内价值最大。 我们朴素的做法是将多重背包拆分成01背包求解，因为每个物品都有有限个，假设第$i$个物品有$j$个，那么跑$j$次01背包即可。 但是这样复杂 ......