HDU3466 01背包

大概意思是給你2個數分别代表物品個數和你帶的錢數，每個物品有3個值，p,q,v，分别表示買該物品所花的錢，買該物品最低所帶的錢，物品的價值。得出最大的價值。

很明顯是01背包。

則狀态轉移方程為:

for(i=0;i<n;i++)

for(j=m;j>=a[i].q;j--)

dp[j]=max(dp[j],dp[j-a[i].p]+a[i].w).

若保證動歸方程無後效性，dp[j-a[i].p]一定要比dp[j]先算，j最小為a[i].q，是以需按q-p從小到大排序。

代碼如下：