這道題看了解題報告後才懂的，第一次遇到這種變形的背包，不過真是很難想到要先按照Q-P排序。。。 下面說一下我對本題的理解。 首先講一下暴力解決，很顯然我們可以用枚舉的方法，對每個物品都有選與不選兩種決策。但即使暴力也存在一個問題，比如對 3 5 6，5 10 5這兩個物品，如果我們的決策是兩個都不選或者是只選其中一個，顯然沒什麼問題，但如果我們要是兩個都選的話，按照之前這個順序有m>=13，但如果把兩個的順序交換一下則m>=10即可，從這裡就可以看出問題的所在了。於是，對任意兩個物品i，j，為了避免上面存在的那種問題，我們可以算出兩種順序所需要的最少金額，若i->j，則至少需要Pi+Qj,若是j->i則至少需要Pj+Qi。如果已知結果是i->j較優的話，則有Pi+Qj<Pj+Qi，即Qi-Pi>Qj-Pj。所以若對之前的物品先按照Q-P由大到小排好序後，然後暴力就可以解決了。但這種暴力其實已有較好的算法可以解決了，即0-1背包，說到這裡原問題就已經完全轉化為了普通的0-1背包了 但還有一點需要要解釋一下，剛才是說暴力是按照Q-P從大到小先排好序，但由於dp與暴力其實正好是兩個逆過程，dp的好處就不再多解釋了，即避免對子問題的重復計算。所以dp前我們是按照Q-P從小到大的順序排好序。 OK，此題總算完滿解決了! [cpp] #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct goods { int p,q,v,d; bool operator<(const goods t)const { return d<t.d; } }g[501]; int dp[5001]; int main() { int n,m,i,j; while(~scanf("%d%d",&n,&m)) { memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d%d%d",&g[i].p,&g[i].q,&g[i].v); g[i].d=g[i].q-g[i].p; } sort(g+1,g+n+1); for(i=1;i<=n;i++) for(j=m;j>=g[i].q;j--) dp[j]=max(dp[j],dp[j-g[i].p]+g[i].v); printf("%d\n",dp[m]); } return 0; }
