解的表示與評價(jià)

在算法設(shè)計(jì)之前，還得設(shè)計(jì)一下解的表示方式（已報(bào)名深蘭ai算法 底部評）。在背包問題中，所要做的決策是拿或者不拿某個(gè)物品，那么這一行為在計(jì)算機(jī)中如何表示比較好呢？

因?yàn)樵搯栴}的決策只有兩種狀態(tài)，所以我們可以用0表示不拿，1表示拿。N個(gè)物品我們就可以用一個(gè)N維的數(shù)組x進(jìn)行表示，當(dāng)：

\[\left\{ \begin{aligned} x[i] & = 0 & 不拿物品i \\ x[i] & = 1 & 拿物品i \end{aligned} \right. \]

此外，我們還得用個(gè)變量表示目標(biāo)值，由于約束的存在，我們還得標(biāo)識該解是否滿足所有約束了……等等，那么就把這堆東西集成到一個(gè)class里面吧：

class kp_solution(): ? ?def __init__(self): ? ? ? ?self.decision ? ?= [] ?# ?決策變量 ? ? ? ?self.total_value = 0 ? # ?decision決策對應(yīng)的目標(biāo)值 ? ? ? ?self.feasible ? ?= False # ?decision決策是否滿足所有約束

現(xiàn)在解已經(jīng)用計(jì)算機(jī)語言表示出來了，如何去評價(jià)一個(gè)解已經(jīng)十分明了了：根據(jù)問題的參數(shù)，計(jì)算決策獲得的價(jià)值，以及判斷該決策是否可行。