網頁

2014年4月29日 星期二

UVa 10130 SuperSale

題意:
    有一家超市有N種商品正在做特價,每種商品數量無限,但規定一個人每種只能買一個,P表示該種商品價值P元,W表示該種商品重W。現在有一家庭共G人,每個人都有不同的背包重量上限MW,問這一家人能買到最高商品價值為多少?

想法:
    背包問題,dp[MW]=k表示重量上限MW的背包裝的物品最多價值k。