wiki-1260-快餐问题 wiki-1260-快餐问题

这道题绝对在我做过的题中排最恶心之首。（以下是网上找的解析，程序是自己写的c++）
本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。状态表示：用p[I,j,k]表示前I 条生产线生产j 个汉堡，k 个薯条的情况下最多可生产饮料的个数。用r[I,j,k]表示第I 条生产线生产j 个汉堡，k 个薯条的情况下最多可生产饮料的个数。态转移方程：
p[I,j,k] = Max{p[I-1,j1,k1]+r[I,j-j1,k-k1]}
(0<=j1<=j,0<=k1<=k,且（j-j1）*p1+(k-k1)*p2<= 第I 条生产线的生产时间)但这样的算法是非常粗糙的，稍加分析可以发现，此算法的时间复杂度为O(N*1004),当N=10 的时候，时间复杂度将达到10*1004=109，这是根本无法承受的。于是，我们必须对算法进行进一步的优化，经仔细观察可以发现：这道题中存在着一个上限值（Min{100 div A, 100 div B, 100 div C}）,这是一个很好的判断条件，他可以帮我们尽早地求出最优解。为什么这样说呢？因为，在动态规划开始前，我们可以先用贪心法算出N条生产线可以生产的套数，如果大于上限值则可以直接输出上限值并退出。否则再调用动态规划，而在动态规划求解的过程中，也可以在每完成一阶段工作便和上限值进行比较，若大于等于上限值就退出，这样一来，就可以尽早的求出解并结束程序。

#include #include #include #include using namespace std; int a,b,c,p1,p2,p3,n,f[11][101][101],t[11]; int main() { freopen("wiki.in","r",stdin); freopen("wiki.out","w",stdout); scanf("%d%d%d%d%d%d%d",&a,&b,&c,&p1,&p2,&p3,&n); for(int i=1; i<=n; i++) scanf("%d",&t[i]); int minn=min(100/a,min(100/b,100/c)); memset(f,-1,sizeof(f)); f[0][0][0]=0; for(int i=1; i<=n; i++) { for(int j=0; j<=minn*a; j++) { for(int k=0; k<=minn*b; k++) { for(int j1=0; j1<=j; j1++) { for(int k1=0; k1<=k; k1++) { if(f[i-1][j-j1][k-k1]!=-1 && t[i]-j1*p1-k1*p2>=0) { if(f[i][j][k] >= minn*c) { j1=j+1; break; } f[i][j][k]=max(f[i][j][k],f[i-1][j-j1][k-k1]+(t[i]-j1*p1-k1*p2)/p3); } } } } } } int ans=0; for(int i=0; i<=minn*a; i++) for(int j=0; j<=minn*b; j++) { ans=max(ans,min(i/a,min(j/b,f[n][i][j]/c))); } printf("%d",ans); }

【wiki-1260-快餐问题】