Z_L_G

题解

总结(20) 训练赛(13)

/ 注册

全部文章 / 题解（共2篇）

算法入门-Min酱要旅行

题意有k个物品，每个物品有体积，求空间为1~m，不带第1~k件的方案数思路无法考虑枚举不带某一个物品，对剩下的物品01背包，复杂度直接爆炸反向思考，可以求解k个物品装满m空间的01背包(每个物品用一次，恰好装满指定体积)，然后再减去必须取某一个物品装满m空间的方案数，就得到去掉某一个物...

多次dp 01背包

2025-07-07

0 30

算法入门-01背包

题意给定n个物品，每个物品由价值和体积，问装入体积为v的背包的最大价值和恰好装满的最大价值思路 01背包问题，对于每个物品考虑装和不装即可，如果不装\装不下，如果装则考虑装进来后的价值，对于每一个物品，在装和不装里取最大即可。注意到，n和val最大都可以取1000，二维数...

dp 01背包

2025-05-01

0 55