夢に僕らで帆を張って
来るべき日のために夜を超え

标签 背包 下的文章

November 11, 2019

洛谷P2014 选课

题意现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程$a$是课程$b$的先修课即只有学完了课程$a$,才能学习课程$b$)。一个学生要从这些课程里选择$M$门课程学习,问他能获得的最大学分是多少?数据范围:$1 \le n,m \le 300$题解树上背包用$dp[u][i]$表示以$u$为根的子树中选择$j$门课的最大学分代码:#include<iostream&...
November 4, 2019

洛谷P1450/HAOI2008 硬币购物

题意硬币购物一共有$4$种硬币。面值分别为$c_1,c_2,c_3,c_4$某人去商店买东西,去了$t$次。每次带$d_i$枚$c_i$硬币,买$s$的价值的东西,请问每次有多少种付款方法数据范围:$d_i,s \le 100000$题解显然不能直接多重背包,会TLE若不考虑限制条件,先当作完全背包处理,再在每次询问的时候将超出部分的情况减去需要减去的部分也是一个完全背包,容量为$s-c_i...
October 27, 2019

洛谷P1455 搭配购买

题意有$n$个物品,$m$个关系,有关系的物品必须一起购买,求最大价值数据范围:$n,w \le 10000,m \le 5000$题解用并查集把有关系的物品合并成$1$个,再用$01$背包即可代码:#include<iostream> #include<cstdio> #include<algorithm> using namespace std; co...
October 16, 2019

洛谷P1776 宝物筛选

题意多重背包数据范围:$0 \le w \le 4 \cdot 10^4,1 \le n \le 100$题解设$w$为价值,$v$为体积,$c$为数量多重背包的状态转移方程为$$f[i][j]=\max(f[i-1][j-kv]+kw)$$其中$k \in [1,c]$由于$i$一定从$i-1$转移而来,所以第一维可以去掉$$f[j]=\max(f[j-kv]+kw)$$但是这样$dp$的...
September 26, 2019

洛谷P2340 奶牛会展

题意有$N$头奶牛,每头奶牛都有智商$S$和情商$F$,要从中选出一些奶牛,要求情商总和和智商总和都不能为负,求情商和智商最大总和数据范围:$1 \le N \le 400,-1000 \le S,F \le 1000$题解选或不选,很像$0/1$背包,于是将其中一个值作为背包容量,另一个作为价值(例如此处将$S$作为容量,$F$作为价值),则可用$f[i]$表示$S=i$时$F$的最大值,...
September 26, 2019

洛谷P1273 有线电视网

题意:树上分组背包数据范围: $2 \le N \le 3000,1 \le M \le N-1$题解:算法:树形dp类似于01背包,考虑滚动数组优化。将每一个节点视为一个背包,其容量即为其子树大小。使用 $dp[u][i]$ 表示以 $u$ 为根节点的子树中,使用 $i$ 个子节点的最大值。可以得出状态转移方程:$$dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[v...