題意：題目大意是說n個人做m項工程，然后給出工人的薪水，和工程按期完工的概率，以及按時完工的酬勞和未按時完工的罰款，要求出最大利潤。。需要注意的 是，薪水輸出的是歐元為單位，輸出的是以分為單位。

解題思路：簡單的背包問題，dp[i][j]表示前i個工程，分配j個人完成的最大期望利潤。dp[i][j] = max{dp[i-1][k] + cost}, 0 <= k <= j

這道題的利潤可能為負，所以初始化不能直接賦0，這里WA了一次。總體不是很難，看懂題意就比較簡單了。

#include<iostream> #include<cstdio> #include<cstring> #define max(a,b) a > b ? a : bconst int maxn = 105; const int inf = 0x7fffffff; int n,m,salary,p[maxn][maxn]; int reward[maxn],punish[maxn]; int dp[maxn][maxn]; //dp[i][j]表示前i個項目共j人做得到的最大利潤int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&m,&n,&salary); //m個項目，n個人for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++)scanf("%d",&p[i][j]);scanf("%d%d",&reward[i],&punish[i]);}for(int i = 0; i <= m; i++)for(int j = 0; j <= n; j++) dp[i][j] = -inf;for(int i = 0; i <= n; i++)dp[1][i] = p[1][i] * (reward[1] - i * salary) - (100 - p[1][i]) * punish[1]; for(int i = 2; i <= m; i++)for(int j = 0; j <= n; j++)for(int k = 0; k <= j; k++){dp[i][j] = max(dp[i][j],dp[i-1][j-k] + p[i][k] * (reward[i] - k * salary) - (100 - p[i][k]) * punish[i]);}int ans = -inf;for(int i = 0; i <= n; i++)ans = max(ans,dp[m][i]);printf("%d\n",ans);for(int i = 0; i <= n; i++)if(ans == dp[m][i])printf("%d ",i);printf("\n");}return 0; }

總結

以上是生活随笔為你收集整理的poj 3459(背包问题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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