題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5501

現在有A1,B1,C1和A2,B2,C2這兩道題，如果先做1再做2的得分是A1-B1*C1+A2-B2*(C1+C2)，如果先做2在做1的得分是A2-B2*C2+A1-B1*(C1+C2),令先做1再做2的得分更高些，那么有A1-B1*C1+A2-B2*(C1+C2) >=?A2-B2*C2+A1-B1*(C1+C2),解得B1*C2>=B2*C1

所以，只要B1*C2>=B2*C1，那么先做題1再做題2的分數就會更高。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int maxn = 1005; struct Node {int a,b,c; }p[maxn]; int n,m,dp[maxn*3];bool cmp(Node A,Node B) {return A.b * B.c > B.b * A.c; }int main() {int t;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++)scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);sort(p+1,p+1+n,cmp);for(int i = 1; i <= n; i++)for(int j = m; j >= p[i].c; j--)dp[j] = max(dp[j],dp[j-p[i].c] + p[i].a - j * p[i].b);int ans = 0; for(int i = 0; i <= m; i++) //這里要從dp[i]中尋找最大，因為dp[i]不一定會最大，因為dp[i]并不一定是遞增的。ans = max(ans, dp[i]); printf("%d\n", ans); }return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的hdu 5501(贪心+01背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。