(dp专题006)hdu 2602 Bone Collector(01背包)

题目链接

题意:容量为V的背包,n个骨头,给出价值和体积,问最多能装多少价值的背包。

思路:01背包裸体。

 

[dp专题005]hdu 1864最大报销额(01背包,垃圾题)

hdu1864题目链接

题意:中文题目,不多说了。

思路:正解是01背包,呵呵呵。

出题人是傻逼吗?

不给数据范围?

以及,正解的01背包基于所有的发票额度的只有2位小数。这是让人猜?

本来看到这题这么恶心时不打算写的…

写了的原因纯粹是为了吐槽傻逼出题[……]

Read more

(dp专题004)hdu 2955Robberies(01背包变形)

题目链接

题意: 给出n个银行 ,以及抢劫每个银行可以得到的价值和被抓的概率,不同银行之间被抓的概率是相互独立的,现在给出安全概率p,只有当概率从小于安全概率时才是安全的,问最多能抢劫多少价值。

思路:一开始很直接就想到把概率算成容量,

于是就成了经典的01背包,然后发现概率是do[……]

Read more