社区讨论

关于“除去一个物品”的背包问题。

2020/12/01 22:21学术版参与者 5已保存回复 11

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

一个问题：

有 $n$ 个物品 $q$ 个询问。第 $i$ 个物品有 $w_i$ 的重量。

对于询问 $i,j,k$ 。回答有多少种选择物品的方案，满足:

不选择物品i

选择的物品总数为j

物品的总重为k

有一个比较显然的做法：处理出前缀和后缀的dp数组

dp_{i,j}

表示选择i个物品总重为j的方案数。

不过好像有更好的做法（O(1)回答查询）。

共 11 条回复，欢迎继续交流。

正在加载回复...