【Codeforces 1132E】Knapsack

Codeforces 1132 E

题意:给\(cnt_i\)个\(i\)(\(1\leq i\leq 8\)),问用这些数所能构成的最大的不超过\(W\)的数。

思路:随机+贪心。。。

我们考虑将贪心和一个奇奇怪怪的随机算法结合在一起取最大值。

  • 贪心:我们枚举所有的\(8\)个数的排列,然后将第\(i\)个数尽量取到能取的最大值,加入答案。

  • 随机:首先我们考虑约束条件\(t\)。\(t\)从\(1\)开始,然后逐步收敛为\(t\times0.999999\),\(t\times0.999999^2\)、。。。

    然后我们随机地考虑一个数\(i\),再看如果当前的数超过了\(w\),那么我们肯定要将\(i\)取的个数压下去,则随机\([0,nowchosen_i\times t]\)中的一个作为新的\(i\)取的个数。否则我们需要将\(i\)取的个数加上去,则随机\(nowchosen_i+[0,(cnt_i-nowchosen_i)\times t]\)中的一个作为新的\(i\)取的个数。

最后取这两种方法的\(max\)即可。

上一篇:MSSQL 分页


下一篇:jquery 3D 标签云