有没有佬来说说哪儿需要修改
by Touris2ts @ 2024-01-04 16:02:14
经证明，这个题目二进制优化写不出来。 当s[i] < k并且s[i]不为0时，s[i] * prices[i]这个数在某些组合计数下是合法的，而在另一些组合计数的情况下是非法的。
1 2 5 10 1
3 2 3 1 10比如这个输入，物品拆分为：
1 2 2 2 5 10 10
前面的1跟2是3个1块钱的分解出来的。
后面的2个2是两个2块钱的硬币。
考虑dp[5]，
有3个1块钱的和一个2两块钱的，
但是在这里两块钱被分成了两种物品，但是他们是同一个种类，所以造成了dp[5]的重复计数。
如果在后面s[i] > 0那里加一个判定条件：s[i] != 之前出现过的k，那么二进制优化后的硬币是：
1 2 2 5 10 10
此时dp[5]不会重复计数。
但是dp[7]计数错误。（漏计了3个1块钱跟2个两块钱的这种情况）
所以二进制优化不是一种可行的方案，那些以时间来否定这种算法的人真是误人子弟。
欢迎反驳。
by Touris2ts @ 2024-01-04 16:20:54
@[Touris2ts](/user/1180143) 多重背包本身就写不出来，与二进制优化无关。多重背包方案会造成计算结果重复，程序会自动将相同价格的硬币看成不同的个体，重复计数，只能用完全背包和容斥原理做，你也可以看看：[楼下帖](https://www.luogu.com.cn/discuss/722310)
by 孔繁臻帅哥 @ 2024-01-05 13:16:05
@[孔繁臻帅哥](/user/365855) 你说的对，这个问题不能用多重背包取决于这个问题的性质，跟二进制优化没关系。
不过大多数人劝退背包暴力求解的原因是即使使用二进制优化的仍然会造成复杂度过高，会给新人一种二进制优化可以解这个问题的错觉。所以我在这里指正这个问题在二进制优化下无解。
by Touris2ts @ 2024-01-05 14:00:45
你说得对
by 孔繁臻帅哥 @ 2024-03-29 11:19:57