第二个买草料的问题怎么感觉那么像[完全背包] 问题.

Question

买 H 磅.
每个商家的各有价格为 Pi. 而且存货无限.
[完全背包] 问题吧.

Answer 1

吉他熊 2022-06-10 15:45:14

对，其实它就是完全背包问题。完全背包问题除了常规DP做法以外，是可以用随机贪心法得到不错的近似解的（甚至随机次数足够多的情况下，也可以得到最优解）。

举这个例子主要是为了从一个比较常见的问题模型，引出随机贪心这种“不那么常规”的做法，因为在很多DP解法不好想，而朴素贪心又明显有反例的时候，随机贪心法往往有很好的效果。完全背包已经有比较成熟的DP解法，不在此列，但对于其他不常见的问题呢？

另外，完全背包问题的DP做法，在第四章《动态规划基础》有讲。

希望可以解答你的疑问 :)

• 提问者 qq_弹簧_3 #1

  谢谢老师的耐心解答, 感觉这个随机贪心的算法有几分玄学.