Stochastic Knapsack

Stocastic Knapsack 应该是指的每个东西的价值或者大小服从某个概率分布而不是定值,当你决定选择这个物品以后其价值就确定了。需要做这个的原因是因为我博弈论的论文需要用到这个东西。

实际上解起来也特别简单,枚举一下自己的操作,假设价值大小是离散的。那么我们就可以简单的对每种价值计算一下贡献乘上概率即可。

如果是离散的话,可以给出一种fptas的做法,和普通背包的fptas一样,把价值大小除以 $\frac{\epsilon}{n}$。仔细计算一下误差不会很大就对了。

这个东西我之前听起来第一眼是觉得不可做,今天闲着想了一下发现非常裸。。。。。。还没去搜论文看,不知道会不会有更好的解。但是有fptas看起来很牛逼就对了。(再次后悔算设没好好学。