題目描述
????某商店打折促銷，滿20減5元撑蒜，現(xiàn)有商品6件，價(jià)格分別為P{5,10,13,9,6}充坑，問如何選擇商品既獲得滿減優(yōu)惠减江，又可花費(fèi)最少？
思路分析
????這個(gè)問題本質(zhì)是一個(gè)"01背包"問題捻爷。記滿減優(yōu)惠的界限為gate辈灼，如果我們購(gòu)買所有商品，那么花費(fèi)totalCost=Σ(Pi)也榄，如果totalCost<gate巡莹，那么無法獲得滿減優(yōu)惠，反之則可以獲得滿減優(yōu)惠甜紫。記gap=totalCost-gate降宅，那我們的問題就轉(zhuǎn)化成，如果選擇商品在總價(jià)值sum不超過gap的情況下使得sum最大囚霸。這就是一個(gè)典型的“01背包問題”了腰根，代碼還請(qǐng)大家自己試著實(shí)現(xiàn)拓型！
