首页 > Min酱要旅行
开通博客写题解
头像 在刷题的单身狗很开心
发表于 2023-10-28 09:35:06
本题如果想要直接去求的话需要对每一个物品去掉的情况进行一个01背包，这样的代价太大全部都会超时的。 那么我们将动态规划式子转换一下，某个物品去掉，背包容积在j下的种类数=背包容积在j下的种类数-某个物品一定要带，背包容积在j下的种类数。 那么某个物品一定要带的情况，其实相当于背包容积在j 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Z_L_G
发表于 2025-07-07 23:46:49
题意 有k个物品，每个物品有体积，求空间为1~m，不带第1~k件的方案数 思路 无法考虑枚举不带某一个物品，对剩下的物品01背包，复杂度直接爆炸 反向思考，可以求解k个物品装满m空间的01背包(每个物品用一次，恰好装满指定体积)，然后再减去必须取某一个物品装满m空间的方案数，就得到去掉某一个物 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”